Rearrange String

You are given a string consisting of lowercase letters. Your task is to rearrange its characters such that no two adjacent characters are the same. If such an arrangement is impossible, output an empty string.

The solution involves using a max‐heap to always select the character with the highest remaining frequency (while avoiding repeating the previously used character) and re‐inserting it back once its turn is over. If at any point no valid character can be chosen, the answer is an empty string.

Note: If there are multiple valid rearrangements, any one of them is acceptable.

inputFormat

The first line of input contains an integer T (1 ≤ T ≤ 100), representing the number of test cases. Each of the following T lines contains a non‐empty string s composed only of lowercase letters.

outputFormat

For each test case, output the rearranged string on a new line. If rearrangement is impossible, output an empty line.

## sample

3
aabb
aaab
abcdefg

abab
abcdefg

</p>