Период слов

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

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

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

В первой строке задано количество тестов d (1 ≤ d ≤ 10). Каждый тест состоит из одной сроки. В начале i-го теста идёт число n_i (2 ≤ n_i ≤ 200000) - длина l слова i. Далее через пробел следует слово w, состоящее из l строчных латинских букв.

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

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

Примеры

Примечание

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

• babcaba — babca — длина 5;

• aabcaba — aabcab — длина 6;

• abbcaba — abbcab — длина 6;

• abacaba — abac — длина 4;

• abababa — ab — длина 2;

• ababcba — ababcb — длина 6;

• ababcaa — ababca — длина 6;

• ababcab — ababc — длина 5.

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