Участникам, использующим язык \t{Python3}, рекомендуется отправлять решения на проверку с использованием интерпретатора \t{PyPy3}.

\medskip

Только что к Штирлицу в руки попало зашифрованное сообщение. Он подозревает, что оно содержит секретную информацию, поэтому активно занимается расшифровкой.

Записка, которой располагает разведчик, представляет собой $k$ полосок, каждая из которых имеет длину $n$ и содержит строчные латинские буквы. Имея большой опыт в расшифровке подобных документов, Штирлиц догадывается, что интересующее его сообщение (расшифровка записки) также является строкой длины $n$, и $i$-я буква этого сообщения совпадает с $i$-й буквой одной из полосок.

По мнению разведчика, \textit{информативностью} строки $s$ называется такое минимальное целое положительное $d$, что существует строка $t$ длины $d$, такая что $s$ представляет собой $t$, повторённую несколько раз. То есть $t$ является минимальным периодом строки, а $d$ его длина. Например, информативность строки <<\texttt{aaaa}>> равна 1, строки <<\texttt{abab}>> --- 2, строки <<\texttt{abcd}>> --- 4.

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