Airport Codes

時間制限 : 8 sec, メモリ制限 : 262144 KB

Airport Codes

空港コード

JAG王国では国内の空港にそれぞれ空港コードを割り当てて識別をしている.

空港コードは,小文字の英語アルファベットで表記した空港の名前をもとに以下の規則で割り当てられる:

  1. 名前の最初の文字と,母音 (a,i,u,e,o) の直後の文字を順に取り出す.
  2. 取り出した文字列が k 文字未満ならそれを空港コードとし, k 文字以上なら,その取り出した文字列の先頭 k 文字を空港コードとして使う.

例えば k = 3 のとき,haneda には hnd , oookayama には ooo , tsu には t というコードが割り当てられる.

しかしこのコードの割り当て方では,違う名前の空港でも同じコードが割り当てられることがあり,混乱を招いてしまう. 空港の名前の一覧が与えられるので,すべての空港のコードが異なるようにできるか判定して,可能な場合はすべての空港コードが異なるようにできる最小の k を求め,不可能な場合はその旨を伝えるプログラムを作成せよ.

Input

入力は100個以下のデータセットからなる. それぞれのデータセットは次の形式で与えられる.

n
s1
...
sn

1行目に空港の数 n (2 ≤ n ≤ 50) が整数で与えられ,続く n 行にはそれぞれ空港の名前 si が文字列で与えられる. 空港の名前は'a'から'z'の小文字の英語アルファベットのみで構成され,いずれも文字数は1以上50以下である. また,与えられる空港の名前はすべて異なる.すなわち,1 ≤ i < jn のとき sisj を満たす.

入力の終わりは1つのゼロだけからなる行で示される.

Output

それぞれのデータセットについて,すべての空港に相異なる空港コードを割り当てられるときは,そのような最小の k を1行に出力せよ. 不可能な場合は,-1を1行に出力せよ.

Sample Input

3
haneda
oookayama
tsu
2
azusa
azishirabe
2
snuke
snake
4
haneda
honda
hanamaki
hawaii
0

Output for Sample Input

1
4
-1
3

Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2015, 2015-06-14
http://acm-icpc.aitea.net/