Music Collection Search

Phil has a huge music collection, and he is picky about what he listens to. Every song has a name, and the name is a string of characters.

His music player has a search box. When Phil types a string into it, the player lists every song whose name contains that string. If exactly one song matches, Phil can press Enter to play it.

Phil hates the mouse and he hates long typing, so he always types the shortest string that matches only the one song he wants right now. Find that optimal query for every song.

The empty string is a valid query. It matches every song.

The first line contains the number of test cases, $T$. $T$ test cases follow. Each test case starts with a line holding the number of songs, $N$. The next $N$ lines each hold one song name. These $N$ songs are Phil's whole collection.

A song name consists of letters, spaces and the hyphen character (-) only. Within one test case all song names are different. Names are compared without regard to case, so dZihan and Dzihan are the same name, and the search ignores case as well.

Limits

• $1 \le T \le 100$
• $1 \le N \le 100$
• The length of a song name is between 1 and 100 characters.

For each test case, first print a line of the form Case #x:, where $x$ is the test case number starting from 1. Then print $N$ lines, one per song, in the order the songs were given.

On each line print the shortest string that makes the search match that song alone, wrapped in double quotes. If several strings are that short, print the lexicographically smallest one. The case of the query is free, so consider both the upper case and the lower case form of every letter when comparing candidates. If no string matches that song alone, print :( without the double quotes.

In the lexicographic order a space comes before a hyphen, a hyphen comes before every letter, and upper case letters come before lower case letters.