테크노배블 (Large)

문제

교수님은 매년 권위 있는 과학 학술대회의 빈 발표 신청서를 연구실 문에 붙여 둔다. 학술대회에서 발표하고 싶은 학생은 신청서에 아직 없는 두 단어짜리 주제를 정해 신청서에 적는다. 마감이 지나면 교수님은 먼저 신청한 학생이 유리하거나 불리해지지 않도록 대학원생 한 명에게 주제의 순서를 무작위로 섞게 한다. 그런 다음 섞인 주제 목록을 당신에게 검토하라고 건넨다.

학술대회 간식이 아주 훌륭해서 몇몇 학생은 가짜 주제로 학술대회에 끼어들려고 한다. 이들은 신청서에 이미 있는 어떤 주제의 첫 번째 단어와, 신청서에 이미 있는 어떤 주제의 두 번째 단어를 골라 (첫 번째 단어를 앞에, 두 번째 단어를 뒤에 두어) 새로운 "주제"를 만든다. 단, 만든 주제가 신청서에 이미 있으면 안 된다. 교수님이 너그러운 편이라 이 전략이 실제로 통할 때도 있다!

가짜 신청자는 독창성이 전혀 없어서 새로운 첫 번째 단어나 두 번째 단어를 스스로 떠올리지 못하고, 신청서에 있는 단어만 쓴다. 또한 이미 있는 첫 번째 단어를 자신의 두 번째 단어로 쓰지 않으며 (그 단어가 신청서에 두 번째 단어로도 이미 있는 경우는 제외), 반대로 두 번째 단어를 첫 번째 단어로 쓰지도 않는다.

제출된 주제 $N$ 개가 모두 적힌 목록이 임의의 순서로 주어진다. 실제로 신청서에 적힌 순서는 알 수 없다. 이 중 가짜일 수 있는 주제는 최대 몇 개인가?

입력

첫째 줄에 테스트 케이스의 수 $T$ 가 주어진다. 이어서 $T$ 개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 $N$ 이 있고, 그 뒤로 $N$ 개의 줄에 서로 다른 주제가 하나씩 주어진다. 각 주제는 영어 대문자로 이루어진 문자열 두 개, 즉 주제의 두 단어가 순서대로 주어진다.

제한

$1 \le T \le 100$
각 단어의 길이는 1 이상 20 이하이다.
한 테스트 케이스 안에서 같은 주제가 두 번 나오지 않는다.
$1 \le N \le 1000$

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 가짜일 수 있는 주제 수의 최댓값이다.

힌트

예제의 1번 케이스에서는 주제가 다음 순서로 신청서에 적혔을 수 있다.

QUAIL BEHAVIOR (진짜)
HYDROCARBON COMBUSTION (진짜)
QUAIL COMBUSTION (가짜)

두 개 이상의 주제가 가짜인 경우는 없다.

2번 케이스에서는 모든 주제가 진짜여야 한다. 어떤 순서로 적혔든, 이미 있는 단어로 목록에 없는 새 주제를 만들 수 있는 시점은 한 번도 없다.

3번 케이스에서는 어느 주제도 가짜일 수 없다. 예를 들어 INTERGALACTIC PLANETARY가 신청서에 처음이자 유일하게 적힌 주제였다면, 가짜 신청자는 INTERGALACTIC을 새 주제의 첫 번째 단어로만, PLANETARY를 새 주제의 두 번째 단어로만 쓸 수 있다. 그러면 만들 수 있는 주제는 INTERGALACTIC PLANETARY뿐인데, 이 주제는 이미 신청서에 있으므로 쓸 수 없다. 따라서 PLANETARY INTERGALACTIC도 진짜 주제여야 한다.