Rearrange String

You are given a string s consisting of lowercase letters. Your task is to rearrange the characters of s so that no two adjacent characters are the same. If it is possible to rearrange the string to satisfy this property, output YES on the first line and the rearranged string on the next line. Otherwise, output NO.

Note: If there are multiple valid rearrangements, you may output any of them.

Hint: A greedy algorithm using a max-heap (priority queue) is an effective approach to solve this problem. In mathematical terms, if the highest frequency of any character exceeds \(\lceil \frac{n}{2} \rceil\) (where \(n\) is the length of the string), then a valid rearrangement is impossible.

inputFormat

The first line contains an integer T (1 ≤ T ≤ 10⁵), the number of test cases. Each of the following T lines contains a non-empty string s consisting of lowercase letters only.

outputFormat

For each test case, if a valid rearrangement exists, output YES on one line and the rearranged string on the next line. Otherwise, output NO. Each test case's output should be printed sequentially.

## sample

3
abac
aaaa
abc

YES
abac
NO
YES
abc

</p>