Rearrange String to Avoid Adjacent Duplicates

You are given a string \(S\) consisting of lowercase alphabets. Your task is to rearrange the characters of \(S\) such that no two adjacent characters are the same.

If such an arrangement is impossible, output "No". Otherwise, output any valid rearrangement.

inputFormat

The input begins with an integer \(T\) representing the number of test cases. Then, \(T\) lines follow, each containing a non-empty string \(S\) comprised only of lowercase letters.

outputFormat

For each test case, output a single line with the rearranged string so that no two adjacent characters are identical, or output "No" if no valid rearrangement exists.

1
aab

aba