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.

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