Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

E. Nearly Shortest Repeating Substring
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

More formally, find the length of the shortest string k such that c=k++kx times for some positive integer x, strings s and c has the same length and cisi for at most one i (i.e. there exist 0 or 1 such positions).

Input

The first line contains a single integer t (1t103) — the number of test cases.

The first line of each test case contains a single integer n (1n2105) — the length of string s.

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

The sum of n over all test cases does not exceed 2105.

Output

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

Example
Input
5
4
abaa
4
abba
13
slavicgslavic
8
hshahaha
20
stormflamestornflame
Output
1
4
13
2
10
Note

In the first test case, you can select k=a and k+k+k+k=aaaa, which only differs from s in the second position.

In the second test case, you cannot select k of length one or two. We can have k=abba, which is equal to s.