Palindromic Rearrangement

You are given a string. Your task is to determine whether it is possible to rearrange the characters of the string to form a palindrome. A palindrome is a string that reads the same backward as forward.

A string can be rearranged into a palindrome if and only if the number of characters that appear an odd number of times is at most one. In mathematical notation, if for the multiset of characters \( S \), the condition
\( \sum_{c \in S} \mathbf{1}\{\text{freq}(c) \mod 2 \neq 0\} \leq 1 \)
holds, then a palindromic rearrangement exists.

If it is possible to form a palindrome, you should print "YES" on one line followed by one valid rearranged palindrome on the next line. If it is not possible, simply print "NO".

inputFormat

The first line contains an integer \(T\) indicating the number of test cases. Each of the following \(T\) lines contains a non-empty string composed of lowercase English letters.

outputFormat

For each test case, if it is possible to rearrange the string to form a palindrome, output two lines: the first line should be "YES" and the second line should be one valid palindrome rearrangement. Otherwise, output only one line with "NO".

1
aabb

YES
abba