음악 컬렉션 검색어

필은 노래를 아주 많이 모아 두었고, 지금 무엇을 들을지 까다롭게 고른다. 노래마다 이름이 하나씩 있고, 이름은 문자열이다.

음악 플레이어에는 검색 기능이 있다. 검색창에 문자열을 입력하면 플레이어는 이름 안에 그 문자열이 들어 있는 노래를 모두 나열한다. 검색에 걸린 노래가 정확히 한 곡이면 필은 엔터 키를 눌러 그 곡을 재생할 수 있다.

필은 마우스를 쓰기 싫어하고 길게 타이핑하는 것도 싫어한다. 그래서 지금 듣고 싶은 그 한 곡만 걸리는 가장 짧은 문자열을 항상 입력한다. 노래마다 그 최적의 검색어를 구하라.

빈 문자열도 검색어로 입력할 수 있다. 빈 문자열은 모든 노래에 걸린다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 노래의 개수 $N$이 주어지고, 다음 $N$개의 줄에 노래 이름이 한 줄에 하나씩 주어진다. 이 $N$곡이 필이 가진 노래 전부다.

노래 이름은 영문자, 공백, 하이픈(-)으로만 이루어진다. 한 테스트 케이스 안의 노래 이름은 모두 서로 다르다. 이름은 대소문자를 구분하지 않아서 dZihan과 Dzihan은 같은 이름이고, 검색도 대소문자를 구분하지 않는다.

제한

• $1 \le T \le 100$
• $1 \le N \le 100$
• 노래 이름의 길이는 1자 이상 100자 이하다.

각 테스트 케이스마다 먼저 Case #x: 형식으로 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이고 1부터 시작한다. 그다음 입력에 주어진 순서대로 노래마다 한 줄씩, 모두 $N$개의 줄을 출력한다.

각 줄에는 그 노래 하나만 검색에 걸리게 하는 가장 짧은 문자열을 큰따옴표로 감싸서 출력한다. 그런 문자열이 여러 개면 사전순으로 가장 앞선 것을 출력한다. 검색어의 대소문자는 자유롭게 고를 수 있으므로, 같은 글자의 대문자 형태와 소문자 형태를 모두 후보에 넣고 비교한다. 그 노래 하나만 걸리게 하는 문자열이 아예 없으면 큰따옴표 없이 :(를 출력한다.

사전순 비교에서는 공백이 하이픈보다 앞서고, 하이픈이 모든 영문자보다 앞서며, 대문자가 소문자보다 앞선다.