E. Почти самая короткая повторяющаяся подстрока
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка $$$s$$$ длиной $$$n$$$, состоящая из строчных латинских символов. Найдите длину самой короткой строки $$$k$$$, такой что несколько (возможно одна) копий $$$k$$$ могут быть сконкатенированы вместе, чтобы образовать строку той же длины, что и $$$s$$$, и при этом имеется не более одного отличающегося символа.

Формально, найдите длину самой короткой строки $$$k$$$, такой что $$$c = \underbrace{k + \cdots + k}_{x\rm\ \text{раз}}$$$ для некоторого положительного целого $$$x$$$, строки $$$s$$$ и $$$c$$$ имеют одинаковую длину и $$$c_i \neq s_i$$$ для не более чем одного $$$i$$$ (т.е. существует $$$0$$$ или $$$1$$$ такая позиция).

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — количество тестов.

Первая строка каждого теста содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — длина строки $$$s$$$.

Вторая строка каждого теста содержит строку $$$s$$$, состоящую из строчных латинских символов.

Сумма $$$n$$$ по всем тестам не превышает $$$2\cdot10^5$$$.

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

Для каждого теста выведите длину самой короткой строки $$$k$$$, удовлетворяющей условиям в условии.

Пример
Входные данные
5
4
abaa
4
abba
13
slavicgslavic
8
hshahaha
20
stormflamestornflame
Выходные данные
1
4
13
2
10
Примечание

В первом примере вы можете выбрать $$$k = \texttt{a}$$$ и $$$k+k+k+k = \texttt{aaaa}$$$, которая отличается от $$$s$$$ только во второй позиции.

Во втором примере вы не можете выбрать $$$k$$$ длиной один или два. Мы можем взять $$$k = \texttt{abba}$$$, которая равна $$$s$$$.