Rearrange String to Avoid Adjacent Duplicates

You are given a string s of length n. Your task is to rearrange the characters in the string so that no two adjacent characters are the same. If it is possible to do so, print one valid rearrangement; otherwise, print NO.

The solution often relies on a greedy approach. One effective method is to use a max heap (or priority queue) to repeatedly select the character with the highest remaining frequency while ensuring that it is not identical to the previously placed character. In mathematical terms, if f(c) is the frequency of character c in the string, then a rearrangement is possible if and only if:

[ \max_{c} f(c) \leq \left\lceil \frac{n}{2} \right\rceil ]

Note: Any valid reordering will be accepted by the judge.

inputFormat

The input is read from stdin and is formatted as follows:

• The first line contains an integer q, representing the number of test cases.
• Each of the following q lines contains a test case. Each test case has an integer n (the length of the string) followed by a space and a string s of length n.

outputFormat

For each test case, output a single line. If a valid reordering exists, print one valid rearranged string; otherwise, print NO.

The output is written to stdout.

## sample

3
4 aabb
3 aaa
5 abcde

abab
NO
abcde

</p>