Problem F: Cycle

Problem F: Cycle

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


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.


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.


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

Sample Input


Sample Output



Bonus problem.