The Shortest Period

We call a string $t$ a period of a string $s$ if $|t| \le |s|$ and $s$ is a prefix of $t^k$ (the string $t$ written $k$ times in a row) for some positive integer $k$. For example, the periods of the word entente are ent, entent, and entente, of lengths $3$, $6$, and $7$. The shortest period of $s$ is its period of smallest length.

A teacher wrote a very long word on the whiteboard. Bytie was not paying much attention to the lesson, so instead he copied into his notebook every word that can be obtained from the whiteboard word by removing exactly one letter. If the whiteboard word has length $n$, the notebook then holds $n$ words, each of length $n-1$. Bytie now wants to pick the notebook word whose shortest period is as short as possible. Given the whiteboard word, report the length of that shortest possible shortest period.

The first line contains one integer $d$ ($1 \le d \le 10$), the number of test cases. Each of the next $d$ lines describes one test case: an integer $n_i$ ($2 \le n_i \le 200000$), the length of the whiteboard word, followed by a single space and the $n_i$-letter word itself, made of lowercase English letters.

Print $d$ lines. The $i$-th line contains one integer: the smallest possible shortest period, taken over all words obtainable from the $i$-th whiteboard word by deleting exactly one letter.

Consider the word ababcaba. The words Bytie writes in his notebook, together with the length of each one's shortest period, are:

Removing the letter c in the fifth position gives abababa, whose shortest period has length $2$, and no other single removal yields a shorter shortest period. Hence the answer is $2$.