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

One of the approaches to find the Longest Palindromic Subsequence(LPS) in a string is to reverse the string and find the longest common subsequence between the original S and reversed S' strings.

I did some further research and found that it is not necessary that LCS(S,S') outputs the longest palindromic subsequence (LPS), instead the LPS is one of the all possible LCSs between S and S'.

So as long as we just have to find the length of LPS and not the LPS string itself the LCS(S,S') approach works fine. But for that it must be proved that if length of LPS is x then there exists no subsequence greater that length x common between S and S'. How do I mathematically or intuitively prove this?