Problem F: Cycle

Problem F: Cycle

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 252  Solved: 77
[Submit][Status][Web Board]

Description

As you know, a cell cycle is start from one end phase to next end phase of Mitosis (or Amitosis). Similarly, let’s define a string cycle. Let T be a substring of S, and S can be generated by T. That means if we append T to T for several times, S will become a substring of T. The string cycle of string S is the smallest length of such T. Now give you a string, please find the string cycle of S.

Input

The first line will be an integer T, which is the number of test cases. (1 <= T <= 10)

For each test case, there will be an integer n in the first line, which is the length of the string.

And then there will be a line with a string S. |S| <= 1000000

S will only contain lower case English letters.

Output

Print an integer for each test case which is the string cycle of S.

Sample Input

1
6
abcabc

Sample Output

3

HINT

Bonus problem.

[Submit][Status]