Rearrangement Feasibility after Character Removal

You are given a string s of length n. You must decide if it is possible to remove exactly one character from s such that the remaining string (of length n-1) can be rearranged into a string where no two adjacent characters are identical. Note that if n-1 is less than 2, then the answer is considered NO.

Let \( f \) be the frequency of the most frequent character in s and \( c \) be the number of characters attaining that frequency. By choosing an optimal removal, the new maximum frequency becomes:

• If \( c = 1 \), it becomes \( f-1 \).
• If \( c > 1 \), it remains \( f \>.

A necessary and sufficient condition for the remaining characters (of total n-1) to be rearranged so that no two adjacent characters are equal is:

[ 2 \times (\text{new maximum frequency}) \le n ]

Output YES if the condition holds; otherwise, output NO.

inputFormat

The input is read from standard input. The first line contains a single integer t representing the number of test cases. Each of the next t lines contains a test case with an integer n (the length of the string) and the string s itself separated by a space.

Example:
3
5 ababa
6 aabbcc
3 aaa

outputFormat

For each test case, output a single line with either YES or NO (without quotes) indicating whether it is possible to remove exactly one character from s such that the remaining characters can be rearranged to form a string with no two adjacent identical characters.

## sample

1
5 ababa

YES

</p>