Game Sort: Part 1

Note: The main parts of the statements of the problems Game Sort: Part 1 and Game Sort: Part 2 are identical, except for the last paragraph. The problems can otherwise be solved independently.

Amir and Badari are playing a sorting game. The game starts with a string $\mathbf{S}$ and an integer $\mathbf{P}$ chosen by an impartial judge. Amir must split $\mathbf{S}$ into exactly $\mathbf{P}$ contiguous non-empty parts (substrings). For example, if $\mathbf{S}$ is CODEJAM and $\mathbf{P} = 3$, Amir can split it as [COD, EJA, M] or [CO, D, EJAM]. Amir cannot split it as [COD, EJAM], [COD, JA, M], [EJA, COD, M], or [CODE, EJA, M].

Then Badari must rearrange the letters within each part so that the list of parts is sorted in non-decreasing lexicographical order. If she can, Badari wins. Otherwise, Amir wins. Given the partition Amir made, can you help Badari win, or say that it is not possible?

The first line contains the number of test cases $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each test case has two lines. The first line contains a single integer $\mathbf{P}$, the number of parts Amir made. The second line contains $\mathbf{P}$ strings $\mathbf{S\_1}, \mathbf{S\_2}, \dots, \mathbf{S\_P}$, representing the parts in order.

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is either POSSIBLE if Badari can win, or IMPOSSIBLE if she cannot. If she can win, output a second line containing $t\_1\, t\_2\, \dots\, t\_{\mathbf{P}}$, where $t\_i$ is a rearrangement of the letters of $\mathbf{S\_i}$, and $t\_i$ is lexicographically earlier than or equal to $t\_{i+1}$ for all $i$. If there are multiple solutions, you may output any one of them.

$1 \le \mathbf{T} \le 100$.

For all $i$, each character of $\mathbf{S\_i}$ is an English uppercase letter from A through Z.

In Sample Case #1, Badari could also win in 5 other ways. Two of them are [CO, JED, MA] and [CO, EJD, MA].

In Sample Case #2, Badari can win simply by leaving all parts as Amir gave them. Other ways are also possible.

In Sample Case #3, Amir has guaranteed a win for himself by leaving Badari no winning option.