%wordperiod   - чемпионат MIPT (май 2011)

\begin{problem}{Wordperiods}{wordperiods.in}{wordperiods.out}{1 c}{256 Мб}

Назовём периодом слова $s$ такое слово $t$, длина которого не превосходит длины слова $s$ и для которого существует такое натуральное число $k$, что слово $s$ является префиксом слова $t^k$ (то есть слова, полученного конкатенацией $k$ копий слова $t$). Например, периодами слова \textbf{xyzxyzx} являются слова \textbf{xyz}, \textbf{xyzxyz}, \textbf{xyzxyzx}.

Пусть имеется некоторое слово $w$ длины $l$. Рассмотрим $l$ слов длины $l-1$, $i-е$ из которых получено из слова $w$ вычёркиванием его $i-й$ буквы. Для каждого из этих слов найдём период наименьшей длины. Выведите наименьшее из получившихся $l$ чисел.

\InputFile

В первой строке входного файла задано целое число $d$ ($1 \leq d \leq 10$) --- количество тестовых примеров. В последующих $d$ строках заданы тестовые примеры, по одному на строку. В начале $i-го$ тестового примера идёт число $n_i$ ($2 \leq n_i \leq 200\,000$) --- длина $l$ слова $w$. Далее через пробел следует слово $w$, состоящее из $l$ строчных латинских букв.

\OutputFile

Для каждого тестового примера выведите в отдельной строке одно число --- минимальную длину периода слова, полученного выбрасыванием из исходного слова одной буквы.

\Example

\begin{example}
\exmp{1
8 ababcaba
}{
2
}%
\end{example}

\Explanation

Для слова w из тестового примера имеем следующие слова, наименьшие периоды и их длины:

\begin{tabular}{ll}
  \textbf{babcaba --- babca} & длина 5 \\
  \textbf{aabcaba --- aabcab} & длина 6 \\
  \textbf{abbcaba --- abbcab} & длина 6 \\
  \textbf{abacaba --- abac} & длина 4 \\
  \textbf{abababa --- ab} & длина 2 \\
  \textbf{ababcba --- ababcb} & длина 6 \\
  \textbf{ababcaa --- ababca} & длина 6 \\
  \textbf{ababcab --- ababc} & длина 5 \\
\end{tabular}

Соответственно, наименьшая из длин равна 2, что и является ответом на тестовый пример.
\end{problem} 