Назовём периодом слова \textbf{s }такое слово \textbf{t}, длина которого не превосходит длины слова \textbf{s} и для которого существует такое натуральное число \textbf{k}, что слово \textbf{s }является префиксом слова \textbf{t^k} (то есть слова, полученного конкатенацией \textbf{k }копий слова \textbf{s}). Например, периодами слова \textbf{xyzxyzx} являются слова \textbf{xyz}, \textbf{xyzxyz}, \textbf{xyzxyzx}. Пусть имеется некоторое слово \textbf{w }длины \textbf{l}. Рассмотрим \textbf{l }слов длины \textbf{l - 1}, \textbf{i}-е из которых получено из слова \textbf{w }вычёркиванием его \textbf{i}-ой буквы. Для каждого из этих слов найдём период наименьшей длины. Выведите наименьшее из получившихся \textbf{l }чисел. \InputFile В первой строке задано количество тестов \textbf{d }(\textbf{1 }≤ \textbf{d }≤ \textbf{10}). Каждый тест состоит из одной сроки. В начале \textbf{i}-го теста идёт число \textbf{n_i} (\textbf{2 }≤ \textbf{n_i} ≤ \textbf{200000}) - длина \textbf{l }слова \textbf{i}. Далее через пробел следует слово \textbf{w}, состоящее из \textbf{l }строчных латинских букв. \OutputFile Для каждого теста выведите в отдельной строке одно число - минимальную длину периода слова, полученного выбрасыванием из исходного слова одной буквы. \Note Для слова \textbf{w }из теста имеем следующие слова, наименьшие периоды и их длины: \begin{itemize} \item \textbf{babcaba} --- \textbf{babca} --- длина \textbf{5}; \item \textbf{aabcaba} --- \textbf{aabcab} --- длина \textbf{6}; \item \textbf{abbcaba} --- \textbf{abbcab} --- длина \textbf{6}; \item \textbf{abacaba} --- \textbf{abac} --- длина \textbf{4}; \item \textbf{abababa} --- \textbf{ab} --- длина \textbf{2}; \item \textbf{ababcba} --- \textbf{ababcb} --- длина \textbf{6}; \item \textbf{ababcaa} --- \textbf{ababca} --- длина \textbf{6}; \item \textbf{ababcab} --- \textbf{ababc} --- длина \textbf{5}. \end{itemize} Соответственно, наименьшая из длин равна \textbf{2}, что и является ответом на тестовый пример.