Problem B
Clever Naming Patterns
Input: Standard Input

Output: Standard Output

 

Piotr is organizing a programming competition consisting of n problems, numbered A, B, C, etc. He wants to name the first problem starting with the letter A, the second problem starting with the letter B, and so on. However, he cannot simply come up with random words for problem titles - that wouldn't make sense. For each problem, he has come up with a list of acceptable names. Help Piotr pick an ordering of the problems and an acceptable name for each one so that each problem's name starts with the correct letter of the alphabet.

 
Input
The first line of input gives the number of cases, N. N test cases follow. Each one starts with n on a line by itself. The next n lines list the possible names for each of the n problems. Each line starts with ki - the number of acceptable names for problem i and lists the names, separated by spaces. Each name is a non-empty string of letters. No two names will be the same, and no two names for the same problem will start with the same letter.

1 ≤ N ≤ 30,
1 ≤ n ≤ 26,
1 ≤ ki ≤ 26.

Output

For each test case, first output the line "Case #x:", where x is the test case number. After that, print n lines listing the n problem names, each with only the first letter capitalized. There is guaranteed to be exactly one solution.

 

Sample Input                                         Output for Sample Input

4
3
2 Apples Oranges
1 Bananas
5 Apricots Blueberries Cranberries Zuccini Yams
1
1 ApPlEs
2
2 a b
1 axe
4
4 Aa Ba Ca Da
3 Ab Bb Cb
2 Ac Bc

1 Ad

 
Case #1:
Apples
Bananas
Cranberries
Case #2:
Apples
Case #3:
Axe
B
Case #4:
Ad
Bc
Cb

Da

Problem setter: Igor Naverniouk