Lexicographical Rearrangement

You are given a string S consisting of lowercase English letters. Your task is to rearrange the characters of S to form the lexicographically smallest string possible such that no two adjacent characters are identical. If there is no possible rearrangement that meets the criteria, output IMPOSSIBLE.

Note: A string A is said to be lexicographically smaller than a string B if at the first position where they differ, the character in A comes before the corresponding character in B in alphabetical order.

The challenge is to both determine whether a valid rearrangement exists and if so, to output the lexicographically smallest valid string.

Mathematically, let \(n = |S|\) and let the frequency of each character be \(f(c)\). A necessary and sufficient condition for a valid rearrangement is that for every character \(c\), \[ f(c) \le \left\lceil \frac{n}{2} \right\rceil. \] If this holds, then there exists at least one rearrangement. Among all valid rearrangements, you must select the one that is smallest in lexicographical order.

inputFormat

The first line contains an integer T denoting the number of test cases.

Each of the next T lines contains a single non-empty string S composed of lowercase English letters.

outputFormat

For each test case, output a single line containing the lexicographically smallest rearranged string with no identical adjacent characters, or IMPOSSIBLE if no such rearrangement exists.

## sample

3
aab
aaab
abc

aba
IMPOSSIBLE
abc

</p>