1393 - 山へ帰そう

時間制限 3 秒 / メモリ制限 256 MB / 得点 12 / Writer syoribu / x 0 / 統計 /


TLE
3sec
MLE
256MB
得点
12

問題

  近年イズア国では、山から街に降りてくる動物に悩まされている。あなたは動物を山へ帰そうと研究を重ね、以下のことを明らかにした。

  • それぞれの動物には固有の名前がついている。
  • 2体の動物について、一方の動物の名前のどこかの位置に1文字を挿入すると、もう一方の動物の名前と一致する場合、これらをペアにして山へ帰すことができる。
  • 一度山へ帰った動物が、再び街に降りてくることはない。

あなたは、街に降りてきた動物を、この方法でどのくらい山へ帰すことができるかを計算することにした。

街に降りてきた動物の名前が与えられたとき、この方法で最大いくつのペアを山へ帰すことができるかを求めるプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$
$str_1$
$str_2$
:
$str_N$

1行目に動物の数$N$ ($2 \leq N \leq 100,000$)が与えられる。続く$N$行に$i$番目の動物の名前を表す文字列$str_i$が与えられる。ただし$str_i$は英小文字と英大文字で構成された10文字以下の文字列である。また、すべての動物の名前は異なる($i \ne j$なら$str_i \ne str_j$)。

出力

山へ帰すことができる動物のペアの数の最大値を出力する。  

入出力例

入力例1

4
aedb
aeb
ebCd
cdE

出力例1

1

入力例2

4
bcD
bD
AbD
bc

出力例2

2