A string of length K is called a nice if the frequency of one of its characters is greater than or equal to floor(K/2). You are given a string s of length N, find the length of longest nice substring.

Input format

• First line: T number of test cases.

• For each test case first line contains N, i.e., length of string s and next line contains the string s itself containing only lower case English letters.

Output format

• For each test case output the length of longest nice substring.

Sample Input

• 1
• 5
• abcde

Sample Output

• 3

Constraints

• T <= 10
• N <= 10^5