Rearrange String to Avoid Adjacent Duplicates

Given a string of length \( n \) consisting of uppercase English letters, determine if it is possible to rearrange the characters of the string so that no two adjacent characters are the same.

The problem can be mathematically formulated as follows:

Find a permutation of the characters of string \( s \) such that for every adjacent characters \( s_i \) and \( s_{i+1} \), \( s_i \neq s_{i+1} \). A necessary and sufficient condition for this is that the maximum frequency \( f_{max} \) of any character satisfies \( f_{max} \leq \lceil \frac{n}{2} \rceil \) (or equivalently \( f_{max} \leq \frac{n+1}{2} \)).

If this condition is met, output "YES"; otherwise, output "NO".

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains a single integer \( t \) representing the number of test cases.
• Each test case consists of two lines:
• The first line contains a single integer \( n \), the length of the string.
• The second line contains the string \( s \) itself, consisting of uppercase English letters.

outputFormat

For each test case, output a single line to standard output (stdout) containing either "YES" if the string can be rearranged such that no two adjacent characters are the same, or "NO" otherwise.

## sample

3
4
AABB
3
AAA
6
AABCDE

YES
NO
YES

</p>