Password-free alphabet arrangement

You bought your young nephew Andrey a full set of wooden English letters, A to Z, one of each. The box is long and narrow, so when the 26 letters sit in a row they read like a 26-letter message.

You log into your online accounts with $N$ different passwords, and you worry that the message contains one of them by accident. Decide whether the 26 letters can be placed in a row, each letter used exactly once, so that no password appears as a contiguous substring.

The first line contains the number of test cases $T$. Each test case takes two lines. The first line contains an integer $N$. The second line contains the $N$ different passwords $P_1, P_2, \ldots, P_N$, separated by spaces. Every password consists of uppercase English letters only.

Limits

• $1 \le T \le 100$
• $1 \le N \le 26$
• $1 \le |P_i| \le 26$
• $P_i \ne P_j$ for $i \ne j$
• A single password may repeat a letter.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1. $y$ is a string that uses each of the 26 uppercase letters exactly once and contains no password as a contiguous substring. When more than one such string exists, print the lexicographically smallest one. When no such string exists, print IMPOSSIBLE in place of $y$.