Rearrange Books

You are given a string s consisting of lowercase letters where each letter represents a type of book. The task is to rearrange the characters of s such that no two adjacent characters are the same. Formally, if the frequency of any character is more than \(\left\lfloor \frac{n+1}{2} \right\rfloor\) where \(n\) is the length of the string, then a valid rearrangement is impossible. Otherwise, output any valid rearrangement.

Example:

• For input aabb, a valid rearrangement is abab.
• For input aaab, rearrangement is not possible.

This problem requires you to implement an efficient greedy algorithm using data structures such as heaps or priority queues.

inputFormat

The input is read from stdin and begins with a single integer T representing the number of test cases. This is followed by T lines, each containing a non-empty string of lowercase letters.

Example:

3
aabb
aab
aaabc

outputFormat

For each test case, output the rearranged string in which no two adjacent characters are the same. If no valid rearrangement exists, output Not Possible. The outputs for all test cases should be printed to stdout, each on a new line.

## sample

3
aabb
aab
aaabc

abab
aba
abaca

</p>