Reorganize String to Avoid Adjacent Duplicates

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, output any valid reorganized string. Otherwise, output IMPOSSIBLE.

The challenge is to determine if such a rearrangement is possible and, if so, to print one valid rearrangement. Use the greedy algorithm with a max-heap (or priority queue) to always pick the most frequent character that is not the same as the previously placed character. The formal condition that must be met to allow a solution is if for every character the frequency does not exceed \(\lceil\frac{n}{2}\rceil\), where \(n\) is the length of the string.

Formally, given a string \(s\) of length \(n\) with character frequencies \(f(c)\), a valid solution exists if and only if for all characters \(c\), \[ f(c) \leq \left\lceil \frac{n}{2} \right\rceil. \]

Note: In cases where there are multiple possible answers, your program can output any one of them.

inputFormat

The input is given from stdin in the following format:

T
s1
s2
... 
sT

Here, the first line contains an integer T representing the number of test cases. Each of the following T lines contains a non-empty string s that represents a test case.

outputFormat

For each test case, output a single line from stdout containing the rearranged string. If no valid rearrangement exists, output IMPOSSIBLE.

## sample

3
aabb
aaab
abc

abab
IMPOSSIBLE
abc

</p>