Optimal Keypad

A mobile phone has a keypad of 12 keys, numbered 1 to 12. Each key is labeled with a string of characters. To type the $n$-th character of a key's string, you press that key $n$ times. The goal is to assign character strings to the keys so that typing words drawn from a dictionary of common words takes as few keystrokes as possible on average.

Figure 1

Take the 30 characters $\{a, b, c, \dots, z, +, *, /, ?\}$ written on a label tape in exactly this order. Cut the tape into 12 non-empty pieces, each containing one or more consecutive characters. Number the pieces (labels) $1$ to $12$ from left to right and assign label $k$ to key $k$. Within a label, the first character costs $1$ keystroke, the second costs $2$, and in general the $n$-th character costs $n$ keystrokes.

Figure 2

For a given dictionary, choose the 11 cutting positions that minimize the total number of keystrokes needed to type every word (which is the same as minimizing the average number of keystrokes per word). The answer is reported as a string of 11 characters in which the $i$-th character is the first character of label $i+1$; the first character of label $1$ is always $a$, so it is omitted.

The first line contains an integer $t$ ($1 \le t \le 10$), the number of test cases. Each test case begins with a line containing an integer $M$ ($1 \le M \le 10000$), the number of common words. Each of the next $M$ lines contains one common word. Every word consists of at most 30 characters from the alphabet $\{a, b, c, \dots, z, +, *, /, ?\}$.

For each test case, print one line containing an optimal cut string. Because several cut strings may achieve the minimum, print the one that is smallest in lexicographic order.