Problem H
Music Collection

Audio Phil has a huge music collection, and he is very particular about the songs he listens to. Each song has a name that is a string of characters. His music player has a search feature that lets Phil type a substring into the search box, and the player then lists all songs whose names contain the substring. If there is exactly one song that matches the search, then Phil can hit the Enter key to play that song.

Phil hates using the mouse, and he doesn’t like typing too much, so he insists on always typing the shortest possible substring that will match exactly the one song that he wants to play at this moment. Could you help him find his optimal search query?

Input

The first line of the input gives the number of test cases $T, 1 \le T \le 100$. $T$ test cases follow. Each one starts with a line containing a single number $N, 1 \le N \le 100$. The next $N$ lines each contain one song name – these are all of the songs in Phil’s collection.

Each song name will consist of only letters, spaces and the hyphen character "-". All songs in Phil’s collection will be unique and at most 100 characters in length. Song names are case insensitive, so "dZihan" is the same is "Dzihan". The search algorithm is also case insensitive.

Output

For each test case, output one line containing "Case #$X$:", where $X$ is the case number (starting from 1). After that, print $N$ lines, one for each song in Phil’s collection, in the order that the songs were given in the input. For each song, print the shortest string of characters that will uniquely find that song. If there are several correct answers, print the lexicographically smallest one. Put double quotes around each string. If there is no correct answer, print ":(" without the double quotes.

Note that upper case letters come lexicographically before lower case letters, hyphen comes before all letters, and space comes before hyphen.

5
6
A Perfect Circle - Gravity
Aimee Mann - You Do
Aqualung - Cinderella
Arcade Fire - Haiti
Art of Noise - Pleure
ATB - Marrakech
2
Hybrid - Altitude
Kings of Convenience - The Build-up
3
aaaaaaaabb
aaaaaaabbb
ababababab
3
butter
fly
butterfly
1
Unknown Artist - Track One

Case #1:
"V"
" D"
"Q"
" F"
"S"
"B"
Case #2:
"A"
"C"
Case #3:
"AAAAAAAA"
"BBB"
"BA"
Case #4:
:(
:(
"RF"
Case #5:
""