Rearrange Books on the Shelf

Ariel has a bookshelf where each book is labeled with a genre represented by a lowercase English letter. She wants to rearrange the books so that no two adjacent books are of the same genre. In other words, given a string \( S \) of letters, rearrange it into a sequence \( S' \) such that for every \( i \) (with \( 1 \leq i < |S'| \)), \( S'_i \neq S'_{i+1} \). If such an arrangement is possible, output the rearranged string; otherwise, output an empty string.

Note: \( |S| \) denotes the length of the string \( S \).

inputFormat

The input is read from standard input (stdin). The first line contains an integer ( T ) representing the number of test cases. Each of the next ( T ) lines contains a non-empty string ( S ) consisting of lowercase English letters. ( S ) represents the initial arrangement of books on the shelf.

outputFormat

For each test case, output the rearranged string on a new line so that no two adjacent characters are identical. If it is not possible to rearrange the string as required, output an empty line.## sample

2
aab
aaab

aba