Как-то раз $$$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