Oxşar adlar

Bir gün n dost "Among us" oynamaq üçün toplandı, lakin onlar istəyirdilər ki, lobbiyə daxil olan hər kəs onların birlikdə oynadığını anlasın. Buna görə də, oxşar başlanğıcı olan ləqəblər seçməyə qərar verdilər, amma hər kəs öz cari ləqəbini bəyəndiyi üçün onu çox dəyişmək istəmirdi.

Kompromis olaraq belə bir qərara gəldilər: hər bir oyunçu öz ləqəbini müəyyən sayda simvola dövri olaraq sürüşdürəcək ki, bütün oyunçuların ləqəblərinin ümumi prefiksi mümkün qədər uzun olsun. s = s[0]s[1]...s[n] sətirinin dövri sürüşməsi s[i] = s[i]s[i+1]..s[n]s[0]s[1]...s[i−1] şəklində olan sətirə deyilir, prefiks isə p[i] = s[0]s[1]...s[i] şəklində olan sətirə deyilir.

Beləliklə, ləqəblərə qayıdaraq: bu məsələnin həllini siz tapmalısınız, çünki oyunçular proqramçı deyillər və bu onlar üçün çox çətindir. Onlara ləqəblərini dövri sürüşdürməklə əldə edə biləcəkləri maksimum ümumi prefiksi tapmağa kömək edin.

Giriş məlumatları

Birinci sətirdə n (1 ≤ n ≤ 10^5) - oyunçuların sayı verilir.

Növbəti n sətirdə oyunçuların ləqəbləri verilir: i-ci sətirdə i-ci oyunçunun ləqəbi s[i] (1 ≤ s[i] ≤ 10^5) - kiçik latın hərflərindən ibarət ardıcıllıq verilir. Bütün ləqəblərin uzunluqlarının cəminin 10^5-dən çox olmadığı təmin edilir.

Çıxış məlumatları

Oyunçuların ləqəblərinə bəzi dövri sürüşmələr tətbiq edərək əldə edə biləcəkləri ən uzun ümumi prefiksin uzunluğunu tapın.