시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 16 7 7 87.500%

문제

영선이의 부모님은 집에서 영어와 프랑스어를 이용해 영선이와 대하한다. 영선이는 많은 단어를 들었지만, 어떤 단어가 프랑스어이고 어떤 단어가 영어인지는 모른다.

영선이는 영어로 이루어진 문장 하나와 프랑스어로 이루어진 문장 하나를 알고있다. 그리고, 영어인지 프랑스어인지 모르는 문장을 여러 개 알고 있다.

단어가 영어 문장에서 나타났으면 이 단어는 영어이고, 프랑스어 문장에서 나타났으면 이 단어는 프랑스어이다.

영선이가 들은 모든 문장이 주어졌을 때, 영어이면서 프랑스어인 단어의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 25)

각 테스트 케이스의 첫째 줄에는 문장의 개수 N이 주어진다. (2 ≤ N ≤ 20) 둘째 줄부터 N개의 줄에는 문장이 주어진다.

문장은 단어로 이루어져 있으며, 단어는 공백으로 구분되어져 있다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 10을 넘지 않는다.

첫 번째 문장은 영어 문장이고, 두 번째 문장은 프랑스어 문장이다. 나머지 문장은 어떤 언어인지 알 수 없는 문장이다.

영어 문장과 프랑스어 문장은 최대 1000개의 단어로 이루어져 있고, 나머지 문장은 최대 10개의 문장으로 이루어져 있다.

출력

각각의 테스트 케이스 마다 영어이면서 프랑스어인 단어의 최소 개수를 출력한다.

예제 입력

4
2
he loves to eat baguettes
il aime manger des baguettes
4
a b c d e
f g h i j
a b c i j
f g h d e
4
he drove into a cul de sac
elle a conduit sa voiture
il a conduit dans un cul de sac
il mange pendant que il conduit sa voiture
6
adieu joie de vivre je ne regrette rien
adieu joie de vivre je ne regrette rien
a b c d e
f g h i j
a b c i j
f g h d e

예제 출력

Case #1: 1
Case #2: 4
Case #3: 3
Case #4: 8

힌트