테크노배블 (Small)

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

학술대회의 간식이 워낙 훌륭해서 거짓으로 학술대회에 끼어들려는 학생도 있다. 이런 학생은 신청서에 이미 있는 어떤 주제의 첫 번째 단어와, 신청서에 이미 있는 어떤 주제의 두 번째 단어를 골라 (첫 번째 단어를 앞에, 두 번째 단어를 뒤에 두고) 합쳐서 새 "주제"를 만든다. 단, 그 주제가 신청서에 이미 있으면 안 된다. 교수님은 열린 마음을 지닌 분이라서 가끔은 이 전략이 실제로 통한다!

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

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

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 $N$이 적힌 한 줄로 시작하고, 그 뒤로 $N$줄이 이어진다. 각 줄은 서로 다른 주제 하나를 나타내며, 영어 대문자로 이루어진 두 문자열, 즉 주제의 두 단어가 순서대로 주어진다.

제한

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

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

예제 1번 케이스에서 가능한 경우 하나는 주제가 다음 순서로 신청서에 적힌 것이다.

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

어떤 경우에도 가짜 주제가 두 개 이상일 수는 없다.

예제 2번 케이스에서는 모든 주제가 진짜여야 한다. 어떤 순서로 적혔더라도, 기존 단어로 목록에 아직 없는 새 주제를 만들 수 있었던 순간은 한 번도 없다.

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