Smallest Period Length

You are given a string S of length \(N\). Your task is to determine the length \(L\) of the smallest substring such that when it is repeated \(\frac{N}{L}\) times, it forms the string S exactly. In other words, find the smallest positive integer \(L\) such that:

\( S = (S[0:L])^{\frac{N}{L}} \)

If no such substring exists other than S itself, then \(L = N\). For example, if \(S = \texttt{ababab}\) then \(L = 2\), and if \(S = \texttt{abcd}\) then \(L = 4\).

Note: The input will consist of multiple test cases.

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases. Each test case is described in one line containing an integer \(N\) and a string \(S\), separated by a space, where \(N\) is the length of \(S\).

outputFormat

For each test case, output a single line containing the smallest period length of the string \(S\).

## sample

3
6 ababab
9 abcabcabc
4 abcd

2
3
4

</p>