У Майка есть n строк s1, s2, ..., sn. Каждая строка состоит из маленьких букв латинского алфавита. За один ход он может выбрать строку si, удалить первый символ и вставить его в конец этой строки. Например, если у него имеется строка «coolmike», то за один ход он может преобразовать эту строку в строку равную «oolmikec».
Теперь Майк задается вопросом: какое минимальное количество ходов необходимо сделать, чтобы все строки стали равными.
Выходные данные
Выведите минимальное количество ходов, которое необходимо сделать, чтобы все строки стали равными, или выведите - 1, если решения не существует.
Примечание
В первом тестовом примере оптимальным образом будет преобразовать все строки в строку «zwoxz».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
xzzwo
zwoxz
zzwox
xzzwo
|
5
|
|
2
|
2
molzv
lzvmo
|
2
|
|
3
|
3
kc
kc
kc
|
0
|
|
4
|
3
aa
aa
ab
|
-1
|