Period of words

Vhod

The first line contains the number of test cases $d$ (1 \leq d \leq 10). Each test case is in one line. The line starts with the number n_i (2 \leq n_i \leq 200000) — the length $l$ of the $i$-th word. Then, separated by a space, is the word $w$ consisting of $l$ lowercase Latin letters.

Izhod

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

Primeri

Opomba

For the word $w$ in the test, the resulting words, their minimal 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 sample test.