#P1950E. Nearly Shortest Repeating Substring

    ID: 8783 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>brute forceimplementationnumber theorystrings*1500

Nearly Shortest Repeating Substring

Description

You are given a string ss of length nn consisting of lowercase Latin characters. Find the length of the shortest string kk such that several (possibly one) copies of kk can be concatenated together to form a string with the same length as ss and, at most, one different character.

More formally, find the length of the shortest string kk such that c=k++kx timesc = \underbrace{k + \cdots + k}_{x\rm\ \text{times}} for some positive integer xx, strings ss and cc has the same length and cisic_i \neq s_i for at most one ii (i.e. there exist 00 or 11 such positions).

The first line contains a single integer tt (1t1031 \leq t \leq 10^3) — the number of test cases.

The first line of each test case contains a single integer nn (1n21051 \leq n \leq 2\cdot10^5) — the length of string ss.

The second line of each test case contains the string ss, consisting of lowercase Latin characters.

The sum of nn over all test cases does not exceed 21052\cdot10^5.

For each test case, print the length of the shortest string kk satisfying the constraints in the statement.

Input

The first line contains a single integer tt (1t1031 \leq t \leq 10^3) — the number of test cases.

The first line of each test case contains a single integer nn (1n21051 \leq n \leq 2\cdot10^5) — the length of string ss.

The second line of each test case contains the string ss, consisting of lowercase Latin characters.

The sum of nn over all test cases does not exceed 21052\cdot10^5.

Output

For each test case, print the length of the shortest string kk satisfying the constraints in the statement.

样例输入 1

5
4
abaa
4
abba
13
slavicgslavic
8
hshahaha
20
stormflamestornflame

样例输出 1

1
4
13
2
10

Note

In the first test case, you can select k=ak = \texttt{a} and k+k+k+k=aaaak+k+k+k = \texttt{aaaa}, which only differs from ss in the second position.

In the second test case, you cannot select kk of length one or two. We can have k=abbak = \texttt{abba}, which is equal to ss.