Song Titles

Interview

Time limit1sMemory limit256 MB

Summary

Rearrange each title into the lexicographically smallest anagram with no equal adjacent letters, or report IMPOSSIBLE when none exists.

Level: Medium5 of 10
Topics: Greedy, Heap, String
Solved: No attempts yet

Problem

An obscure instrumental rock band plays on the edge of the Leiden music scene, and all of its members study at Leiden University. They call themselves naaagrm, which is an anagram of an existing Swedish word, and every one of their song titles is an anagram of an existing word too. Many people struggle with the band name, because they do not know how to pronounce the triple a. The band therefore decided to reorder the letters of every song title so that no two consecutive letters are the same. Doing that by hand takes a long time, so they asked you for help.

Input

The first line contains an integer $T$ , the number of test cases. Each of the next $T$ lines contains one string, the current title of a song.

$1 \le T \le 100$
Each string consists of lowercase letters only and has length between $1$ and $10^5$ .
The total length of all strings in one input is at most $2 \times 10^5$ .

Output

For each test case, print on one line an anagram of the given string in which no two consecutive letters are the same. If several such anagrams exist, print the lexicographically smallest one. If no such anagram exists, print IMPOSSIBLE instead.

Examples2

Example 1

Input

5
naaagrm
hiking
snaaan
banana
aaaaaaargh

Expected output

agamanr
ghikin
ananas
abanan
IMPOSSIBLE

Example 2
Input
```
4
a
zz
ab
aab
```
Expected output
```
a
IMPOSSIBLE
ab
aba
```