외계 운율

외계 탐사 중에 외계 시의 흔적이 발견되었다. 언어학자 팀에 따르면 외계어의 각 단어에는 정확히 한 위치(글자)에 강세가 있다. 단어에서 강세가 있는 글자부터 끝까지의 부분을 강세 접미사라고 부른다. 두 단어의 강세 접미사가 서로 같으면 두 단어는 운이 맞는다고 한다. 예를 들어 PROL과 TARPOL은 두 단어 모두 강세가 O 또는 L에 있으면 운이 맞는다. 강세가 R에 있거나, PROL의 R과 TARPOL의 P에 있거나, PROL의 O와 TARPOL의 L에 있으면 운이 맞지 않는다.

외계 시의 일부일 수 있는 단어 $N$개의 목록이 있다. 각 단어의 강세 위치는 모른다. 단어 중 0개 이상을 버릴 수 있고, 남은 단어에 강세 위치를 정한 뒤 단어들을 두 개씩 짝지을 수 있다. 각 단어는 자기 짝과만 운이 맞고, 다른 짝의 어떤 단어와도 운이 맞지 않아야 한다.

이런 방식으로 짝지을 수 있는 단어의 최대 개수를 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 나온다. 각 테스트 케이스는 정수 $N$만 적힌 줄로 시작한다. 그 뒤 $N$개의 줄에 대문자 영어 알파벳으로 이루어진 문자열 $W_i$가 한 줄에 하나씩 주어진다. 한 테스트 케이스 안의 단어는 모두 서로 다르다. 같은 단어라도 테스트 케이스마다 강세 위치는 다를 수 있다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. $x$는 테스트 케이스 번호(1부터 시작), $y$는 위 조건을 만족하는 단어 부분집합의 최대 크기이다.

• $1 \le T \le 100$.
• 모든 $i$에 대해 $1 \le |W_i| \le 50$.
• 모든 $i$에 대해 $W_i$는 대문자 영어 알파벳으로만 이루어진다.
• $i \ne j$이면 $W_i \ne W_j$. 한 테스트 케이스 안에서 단어는 중복되지 않는다.

예시 1에서는 적절히 강세를 정하면 두 단어가 운이 맞으므로, 최대 부분집합은 입력 전체이다.

예시 2에서는 강세를 어떻게 정하더라도 운이 맞는 단어 쌍이 없다. 어떤 두 접미사든 적어도 마지막 글자가 다르기 때문이다. 따라서 최대 부분집합은 공집합이며 크기는 0이다.

예시 3에서는 여섯 단어를 모두 쓸 수 있다. CODEJAM과 JAM은 J에, HAM과 NALAM은 마지막 A에, HUM과 NOLOM은 M에 강세를 둔다.

예시 4에서는 어떤 두 단어든 운이 맞게 만들 수 있지만, 강세를 모두 I로 두어야만 가능하다. 짝을 두 쌍 이상 더하면 서로 다른 짝의 단어끼리도 운이 맞게 된다. 따라서 입력 단어 중 아무 두 개를 고른, 크기 2인 부분집합이 최대이다.