Topic below
The Description

In the use of mobile input English words or Chinese pinyin, we usually is the use of mobile phones in the Numbers 0 to 9 key, under normal circumstances, the corresponding ABC in 2, 3 corresponding DEF, four corresponding ghi, corresponding JKL 5, 6 corresponding mno, corresponding PQRS 7, 8 corresponding tuv, 9 corresponding wxyz, take a look at your mobile phone number keys corresponding relationship with the letter is it? So, after we enter a string of Numbers, cell phone input method software can automatically lists the most likely candidate words or Chinese characters, so this feature is how to achieve?
In fact, the principle is very simple, when we enter a number, input method software will find the most commonly used from all possible combination of letters and most likely a combination of the columns in the top position of the candidate words, input number 5869872, for example, it represents all of the possible letter combinations are: JTMWTPA JTMWTPB... ,

Please design a program to input a set of number (not more than 11) output all possible combination of letters,
Note: the number 1 corresponding to the characters' * ', corresponding characters' 0 '(space),
Input

Said the first line of an integer n, then n group test data, test data of two lines in each group, the first line of an integer m (m<12) (m<=0 to re-enter) said the number of digits, and the next line of a string of Numbers,
The Output

For each test case output lines, the first line of output all letter combinations number T, the following T lines according to the dictionary ascending line output a combination,
The Sample Input

2
1
9
3
120
The Sample Output

4
W
X
Y
Z
3
* A
* B
* C


Heard with DFS can do but they always don't know how to choose