Пораките кои се праќале меѓу окупаторските сили за време на Втората светска војна биле шифрирани. Шифрираните пораки претставувале низи од знаците a и b.

Тјуринг имал за задача да ги дешифрира. Дадени му биле N шифрирани пораки (1<N<5). Тој бил уверен дека во секоја порака некои изрази се повторуваат, па затоа и шифрираните пораки би требало да содржат исти подстрингови. За да ја реши задачата тој прво сакал да дознае кој е најдолгиот подстринг кој го има во сите шифрирани пораки. Познато е дека најдолгиот подстринг има најмногу 60 знаци.

Ваша задача е да му помогнете на Тјуринг со тоа што ќе го најдете најдолгиот подстринг кој го има во сите шифрирани пораки.

Да напомнеме дека секогаш ќе постои ваков подстринг.

Забелешка:

Во 30% од случаите вкупната должина на сите шифрирани пораки е помала од 101.

Во 55% од случаите вкупната должина на сите шифрирани пораки е помала од 3 501.

Во 80% од случаите вкупната должина на сите шифрирани пораки е помала од 10 001.

Во 100% од случаите вкупната должина на сите шифрирани пораки е помала од 50 001.

Влез

Во првиот ред е даден бројот на шифрирани пораки N (1<N<5). Во секој од следните N редови е запишана по една шифрирана порака. Шифрираните пораки се стрингови кои ги содржат исклучиво буквите a и b.

Излез

Должината L на најдолгиот подстринг кој се јавува во сите шифрирани пораки (L<=60).

Ограничувања

Временско ограничување: 600 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
влез
2
abb
b

излез
1

влез
2
abaabab
babaabbbb

излез
5

Објаснување за првиот тест пример: Најдолгиот подстринг кој го има во двете шифрирани пораки е b. Овој подстринг има должина 1.

Објаснување за вториот тест пример: Најдолгиот подстринг кој го има во двете шифрирани пораки е аbааb. Овој подстринг има должина 5.