Похожие имена
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как-то раз $$$n$$$ друзей собрались сыграть в «Among us», но при этом они хотели, чтобы каждый человек, заходящий в лобби, понимал, что они играют вместе. Для этого они решили выбрать никнеймы с похожим началом, но поскольку каждому дорог его текущий никнейм, никто не хочет его сильно изменять.

В качестве компромисса было принято следующее решение: каждый игрок сдвинет свой никнейм по циклу на какое-то количество символов так, чтобы общий префикс никнеймов всех игроков был как можно длиннее. Циклическим сдвигом строки $$$s = s_0 s_1 \ldots s_n$$$ называется строка вида $$$s^i = s_i s_{i+1} \ldots s_n s_0 s_1 \ldots s_{i - 1}$$$, а префиксом — строка вида $$$p^i = s_0 s_1 \ldots s_i$$$.

Так вот, возвращаясь к никнеймам: решить эту задачу предстоит вам, потому что игроки — не программисты, и для них это слишком сложно. Помогите им найти максимальный общий префикс, который можно получить, сдвинув их никнеймы по циклу.

Входные данные

В первой строке задано число $$$n$$$ — количество игроков ($$$1 \leqslant n \leqslant 10^5$$$).

В следующих $$$n$$$ строках заданы никнеймы игроков: на $$$i$$$-й строке дан никнейм $$$i$$$-го игрока $$$s_i$$$ — последовательность строчных латинских букв ($$$1 \leqslant |s_i| \leqslant 10^5$$$). Гарантируется, что сумма длин всех никнеймов не превосходит $$$10^5$$$.

Выходные данные

Найдите длину наибольшего общего префикса, который могут получить игроки, применив к своим никнеймам какие-то циклические сдвиги.

Примеры

Входные данные
4
abacada
abracadabra
rxacadd
dzzzaca
Выходные данные
4
Входные данные
2
abacaba
acabaab
Выходные данные
7