외계인의 운율

외계 탐사를 하던 중, 외계 시의 흔적을 발견했다! 언어학자들로 구성된 팀은 외계 언어의 각 단어에서 정확히 한 위치(글자)에 강세가 있으며, 강세가 있는 글자부터 시작하는 단어의 부분을 강세 접미사라고 부른다는 사실을 알아냈다. 두 단어의 강세 접미사가 모두 같으면 두 단어가 운을 맞춘다고 한다. 예를 들어, PROL와 TARPOL는 두 단어 모두에서 강세가 있는 글자가 O 또는 L이면 운을 맞추지만, 강세가 있는 글자가 R들이거나, PROL의 R와 TARPOL의 P이거나, PROL의 O와 TARPOL의 L이면 운을 맞추지 않는다.

외계 시의 일부일 수도 있는 N개의 단어 목록을 복원했다. 안타깝게도 각 단어에서 어느 글자에 강세가 있는지는 알지 못한다. 이 단어들을 없거나 그 이상 버리고, 남은 단어들에 강세가 있는 글자를 지정한 다음, 각 단어가 자기 쌍의 다른 단어하고만 운을 맞추고 다른 쌍의 어떤 단어와도 운을 맞추지 않도록 이 단어들을 쌍으로 배치할 수 있다고 생각한다.

이런 방식으로 쌍을 이루어 배치할 수 있는 단어 수의 최댓값을 구하고자 한다.

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. 모든 i에 대해, 1 ≤ $W_{i}$의 길이 ≤ 50. 모든 i에 대해, $W_{i}$는 영문 대문자로 이루어진다. 모든 i ≠ j에 대해, $W_{i}$ ≠ $W_{j}$. (한 테스트 케이스 안에서는 단어가 반복되지 않는다.)

테스트 세트 1 (공개)

2 ≤ N ≤ 6.

테스트 세트 2 (비공개)

2 ≤ N ≤ 1000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 하나의 정수 N이 있는 줄로 시작한다. 그다음 N개의 줄이 주어지며, 각 줄에는 서로 다른 단어를 나타내는 영문 대문자 문자열 $W_{i}$가 들어 있다. 서로 다른 테스트 케이스에서는 같은 단어의 강세 위치가 다를 수 있음에 유의한다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 위에서 설명한 조건을 충족하는 가장 큰 단어 부분집합의 크기이다.

예제 케이스 #1에서는 위에서 설명한 것처럼 강세를 적절히 지정하면 두 단어가 운을 맞출 수 있으므로, 가장 큰 부분집합은 입력 전체이다.

예제 케이스 #2에서는 어떤 두 접미사도 적어도 마지막 글자가 다르기 때문에, 강세를 어떻게 지정하더라도 어떤 두 단어도 운을 맞출 수 없다. 따라서 가장 큰 부분집합은 크기가 0인 공집합이다.

예제 케이스 #3에서는 CODEJAM와 JAM의 J들, HAM와 NALAM의 마지막 A들, 그리고 HUM와 NOLOM의 M들에 강세를 두면 단어 집합 전체를 사용할 수 있다.

예제 케이스 #4에서는 어떤 두 단어도 운을 맞추게 할 수 있지만, 그러려면 강세가 있는 글자를 항상 I로 정해야 한다. 따라서 부분집합에 두 쌍을 추가하면 서로 다른 쌍의 단어들이 운을 맞추게 된다. 그러므로 입력 단어 중 아무 2개나 골라 크기가 2인 부분집합만 만들 수 있다.