Rearrange String

Problem Statement:

You are given a string s consisting of lowercase English letters. Your task is to rearrange the characters of the string so that no two adjacent characters are the same. If there is no way to obtain such a rearrangement, output IMPOSSIBLE (in uppercase).

One common approach to solve this problem is to use a greedy algorithm with a max-heap (priority queue) to always select the character with the highest remaining frequency that is not equal to the previously placed character. A necessary condition for the existence of a solution is that for a string of length n, no character appears more than \( \lceil n/2 \rceil \) times.

Note: Any valid rearrangement that meets the criteria is acceptable.

inputFormat

The input is given via STDIN. The first line contains an integer T representing the number of test cases. Each of the following T lines contains a test case. Each test case consists of an integer n and a string s separated by a space, where n denotes the length of the string s.

outputFormat

For each test case, output the rearranged string on a new line. If it is impossible to rearrange the string such that no two adjacent characters are the same, output IMPOSSIBLE. (Note that IMPOSSIBLE should be printed in uppercase.)

All output should be written to STDOUT.

## sample

3
6 aaabbc
3 aaa
7 aabbccd

ababac
IMPOSSIBLE
abcabcd

</p>