Retos de programación - 015: Colección de música

Phil Audio tiene una gran colección de música, y es muy particular con las canciones que escucha. Cada canción tiene un nombre, que es una cadena de caracteres. Su reproductor de música tiene una función de búsqueda que permite a Phil escribir una subcadena en el cuadro de búsqueda, y el reproductor, a continuación, enumera todas las canciones cuyos nombres contengan la subcadena. Si no es exactamente una canción que coincide con la búsqueda, entonces Phil lo puede pulsar la tecla Intro para escuchar esa canción.

Phil odia usar el ratón, y que no le gusta escribir mucho, así que insiste en escribir siempre la subcadena más breve posible que coincide exactamente con la canción que quiere escuchar en este momento. ¿Podrías ayudarle a encontrar a su consulta de búsqueda óptima?

Entrada

La primera línea de la entrada da el número de casos de prueba (T), y a continuación los T casos de prueba. Cada uno comienza con una línea que contiene un único número de N. Las siguientes N líneas contienen un nombre de la canción cada una (que son todas las canciones de la colección de Phil).

Cada nombre de canción estará formado por letras, espacios y el carácter guión (-). Todas las canciones de la colección de Phil son únicas (no hay duplicadaos) y de no más de 100 caracteres de longitud. Los nombres de las canciones pueden estar en mayúsculas y minúsculas, por lo que "dZihan" es la misma es "Dzihan". El algoritmo de búsqueda es también insensible a mayúsculas y minúsculas.

Salida

Para cada caso de prueba, la salida comenzará con una línea que contiene "Caso #x:", donde x es el número de caso (a partir de 1). Después de eso, se mostrarán las N líneas, una para cada canción en la recopilación de Phil, en el orden que las canciones se dieron en la entrada. Para cada canción, se debe imprimir la cadena de caracteres más corta que se encuentra únicamente en esa canción. Si hay varias respuestas correctas, se tomará la primera en orden lexicográfico. Se debe mostrar comillas alrededor de cada cadena. Si no hay una respuesta correcta, se escribirá ":(" sin las comillas dobles.

Tenga en cuenta que las letras mayúsculas aparecen lexicográficamente antes de letras minúsculas, el guión está antes que todas las letras, y en el espacio está antes de guión.

(Asegúrate de que has leído las preguntas frecuentes antes de plantear tu solución)