테크노배블

매년 교수님은 권위 있는 과학 연구 학회의 빈 참가 신청서를 연구실 문에 붙인다. 학생이 학회에서 발표하고 싶다면, 신청서에 아직 없는 두 단어로 된 주제를 골라 신청서에 적는다. 마감 기한이 지나면 교수님은 일찍 신청한 학생에게 유리하거나 불리한 편향을 피하기 위해 대학원생 한 명에게 주제들을 무작위 순서로 배열하게 한다. 그런 다음 검토할 주제들을 당신에게 제시한다.

학회에서 제공하는 간식이 훌륭하기 때문에, 일부 학생들은 속임수를 써서 학회에 참가하려 한다. 이들은 신청서에 이미 있는 어떤 주제의 첫 번째 단어와 신청서에 이미 있는 어떤 주제의 두 번째 단어를 골라, 둘을 결합하여(첫 번째 단어를 앞에, 두 번째 단어를 뒤에 놓아) 새로운 "주제"를 만든다(신청서에 이미 없는 경우에만). 교수님은 열린 마음을 지녔기 때문에 이 전략이 실제로 통할 때도 있다!

속임수를 쓰는 학생들은 전혀 독창적이지 않아 새로운 첫 번째 단어나 두 번째 단어를 스스로 생각해 낼 수 없으며, 반드시 신청서에 있는 기존 단어를 사용해야 한다. 또한 기존의 첫 번째 단어를 자신의 두 번째 단어로 사용하려 하지 않으며(그 단어가 신청서에 두 번째 단어로도 이미 존재하는 경우는 제외), 그 반대도 마찬가지이다.

제출된 N개의 모든 주제가 임의의 순서로 주어진다. 이들이 실제로 신청서에 적힌 순서는 알 수 없다. 그중 속임수로 만들어졌을 수 있는 주제 수의 최댓값은 얼마인가?

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ 각 단어의 길이 ≤ 20. 한 테스트 케이스 안에서 같은 주제가 반복되지 않는다.

작은 데이터 세트(테스트 세트 1 - 공개)

1 ≤ N ≤ 16.

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ N ≤ 1000.

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

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 속임수로 만들어졌을 가능성이 있는 주제 수의 최댓값을 나타내는 정수이다.

예제 케이스 #1에서 가능한 경우 중 하나는 주제들이 다음 순서로 신청서에 추가된 경우이다.

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

주제 중 하나보다 많은 수가 가짜일 수 있는 경우는 없다.

예제 케이스 #2에서는 모든 주제가 진짜여야 한다. 어떤 순서로 적혔든, 어느 시점에도 기존 단어들을 사용해 목록에 아직 없는 새로운 주제를 만드는 것은 불가능했을 것이다.

예제 케이스 #3에서는 어느 주제도 가짜일 수 없다. 예를 들어 INTERGALACTIC PLANETARY이 신청서에 처음이자 유일하게 적힌 주제였다면, 속임수를 쓰는 학생은 새 주제의 첫 번째 단어로 INTERGALACTIC만 사용할 수 있고, 새 주제의 두 번째 단어로 PLANETARY만 사용할 수 있었을 것이다... 하지만 만들 수 있었던 유일한 주제는 INTERGALACTIC PLANETARY이고, 이는 이미 신청서에 있었으므로 사용할 수 없었을 것이다. 따라서 PLANETARY INTERGALACTIC도 진짜 주제였어야 한다.