Period of words

Let's define a period of a word s as a word t, whose length does not exceed that of s, and for which there exists a natural number k such that s is a prefix of the word t^k (meaning the word formed by concatenating k copies of t). For instance, the periods of the word xyzxyzx are xyz, xyzxyz, and xyzxyzx.

Consider a word w with a length of l. From this word, derive l words each of length l - 1, where the i-th word is created by removing the i-th letter from w. For each of these derived words, determine the period of the smallest length. Your task is to output the smallest of these l period lengths.

Input

The first line contains the number of test cases d (1 ≤ d ≤ 10). Each test case is described in one line. The line starts with the number n_i (2 ≤ n_i ≤ 200000)—the length l of the word i. Following this, separated by a space, is the word w, which consists of l lowercase Latin letters.

Output

For each test case, output a single number on a new line—the minimum length of the period of the word obtained by removing one letter from the original word.

Examples

Note

For the word w given in the test, the derived words, their smallest periods, and their lengths are as follows:

• babcaba — babca — length 5;

• aabcaba — aabcab — length 6;

• abbcaba — abbcab — length 6;

• abacaba — abac — length 4;

• abababa — ab — length 2;

• ababcba — ababcb — length 6;

• ababcaa — ababca — length 6;

• ababcab — ababc — length 5.

Thus, the smallest length is 2, which is the answer for the test example.