問題
近年イズア国では、山から街に降りてくる動物に悩まされている。あなたは動物を山へ帰そうと研究を重ね、以下のことを明らかにした。
- それぞれの動物には固有の名前がついている。
- ２体の動物について、一方の動物の名前のどこかの位置に１文字を挿入すると、もう一方の動物の名前と一致する場合、これらをペアにして山へ帰すことができる。
- 一度山へ帰った動物が、再び街に降りてくることはない。
あなたは、街に降りてきた動物を、この方法でどのくらい山へ帰すことができるかを計算することにした。
街に降りてきた動物の名前が与えられたとき、この方法で最大いくつのペアを山へ帰すことができるかを求めるプログラムを作成せよ。
入力
入力は以下の形式で与えられる。
$N$ $str_1$ $str_2$ : $str_N$
１行目に動物の数$N$ ($2 \leq N \leq 100,000$)が与えられる。続く$N$行に$i$番目の動物の名前を表す文字列$str_i$が与えられる。ただし$str_i$は英小文字と英大文字で構成された10文字以下の文字列である。また、すべての動物の名前は異なる($i \ne j$なら$str_i \ne str_j$)。
出力
山へ帰すことができる動物のペアの数の最大値を出力する。
入出力例
入力例１
4 aedb aeb ebCd cdE
出力例１
1
入力例２
4 bcD bD AbD bc
出力例２
2