Період слів

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

Розглянемо слово w довжини l. З нього можна утворити l слів довжини l - 1, кожне з яких отримане шляхом видалення i-ої літери з w. Для кожного з цих слів визначимо період найменшої довжини. Виведіть найменше з отриманих 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, що і є відповіддю на тестовий приклад.