Rearrange String: Avoid Adjacent Duplicates

You are given a string S consisting of lowercase letters. Your task is to rearrange the characters of S such that no two adjacent characters are the same. If it is possible to rearrange the string under this constraint, output any valid rearrangement; otherwise, output NO.

The problem can be approached using a greedy algorithm combined with a priority queue. In particular, let \(f(c)\) denote the frequency of a character \(c\) in S. A necessary condition for a valid rearrangement is that for every character \(c\),

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

If no valid order exists, simply output NO.

inputFormat

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

1. The first line contains a single integer \(T\) representing the number of test cases.
2. Each of the next \(T\) lines contains a single string \(S\) composed only of lowercase letters.

It is guaranteed that \(1 \leq T \leq 10^5\) and \(1 \leq |S| \leq 10^5\) across all test cases.

outputFormat

For each test case, output a single line to stdout containing the rearranged string in which no two adjacent characters are the same. If no such rearrangement is possible, output NO.

## sample

3
aabb
aaab
abb

abab
NO
bab

</p>