A string is called boring if all the characters of the string are same.

You are given a string S of length N, consisting of lowercase english alphabets. Find the length of the longest boring substring of S which occurs more than once.

Note that if there is no boring substring which occurs more than once in S, the answer will be 0.

A substring is obtained by deleting some (possibly zero) elements from the beginning of the string and some (possibly zero) elements from the end of the string.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of two lines of input.
• The first line of each test case contains an integer N, denoting the length of string S.
• The next contains string S.

------ Output Format ------

For each test case, output on a new line, the length of the longest boring substring of S which occurs more than once.

------ Constraints ------

$1 ≤ T ≤ 1000$
$1 < N ≤ 2\cdot 10^{5}$
- The sum of $N$ over all test cases won't exceed $5\cdot 10^{5}$.
$S$ consists of lowercase english alphabets.

----- Sample Input 1 ------
4
3
aaa
3
abc
5
bcaca
6
caabaa

----- Sample Output 1 ------
2
0
1
2

----- explanation 1 ------
Test case $1$: The length of the longest boring substring that occurs more than once is $2$. The boring substring of length $2$ occurring more than once is aa.

Test case $2$: There is no boring substring which occurs more than once. Thus, the answer is $0$.

Test case $3$: The length of the longest boring substring that occurs more than once is $1$. Some boring substrings of length $1$ occurring more than once are c and a.

Test case $4$: The length of the longest boring substring that occurs more than once is $2$. The boring substring of length $2$ occurring more than once is aa.

见题面

见题面