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

В качестве компромисса было принято следующее решение: каждый игрок сдвинет свой никнейм по циклу на какое-то количество символов так, чтобы общий префикс никнеймов всех игроков был как можно длиннее. Циклическим сдвигом строки s = s0s1...sn называется строка вида si = sisi+1..sns0s1...si−1, а префиксом - строка вида pi = s0s1...si.

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

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

В первой строке задано число n (1 ≤ n ≤ 105) - количество игроков.

В следующих n строках заданы никнеймы игроков: на i-й строке дан никнейм i-го игрока si (1 ≤ si ≤ 105) - последовательность строчных латинских букв. Гарантируется, что сумма длин всех никнеймов не превосходит 105.

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

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