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

В качестве компромисса было принято следующее решение: каждый игрок сдвинет свой никнейм по циклу на какое-то количество символов так, чтобы общий префикс никнеймов всех игроков был как можно длиннее. Циклическим сдвигом строки s = s₀s₁...s_n называется строка вида sⁱ = s_is_i+1...s_ns₀s₁...s_i−1, а префиксом - строка вида pⁱ = s₀s₁...s_i.

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

Формат входных данных

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

Формат выходных данных

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

Пример