시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 17 8 8 88.889%

문제

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

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

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

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

입력

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

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

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

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

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

출력

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

예제 입력 1

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

예제 출력 1

Case #1: 1
Case #2: 4
Case #3: 3
Case #4: 8
W3sicHJvYmxlbV9pZCI6IjEyMTQzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNjAxXHVjNWI0XHVjNjQwIFx1ZDUwNFx1Yjc5MVx1YzJhNFx1YzViNCAoU21hbGwpIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2MDFcdWMxMjBcdWM3NzRcdWM3NTggXHViZDgwXHViYWE4XHViMmQ4XHVjNzQwIFx1YzlkMVx1YzVkMFx1YzExYyBcdWM2MDFcdWM1YjRcdWM2NDAgXHVkNTA0XHViNzkxXHVjMmE0XHVjNWI0XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWM2MDFcdWMxMjBcdWM3NzRcdWM2NDAgXHViMzAwXHVkNjU0XHVkNTVjXHViMmU0LiBcdWM2MDFcdWMxMjBcdWM3NzRcdWIyOTQgXHViOWNlXHVjNzQwIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWI0ZTRcdWM1YzhcdWM5YzBcdWI5Y2MsIFx1YzViNFx1YjVhNCBcdWIyZThcdWM1YjRcdWFjMDAgXHVkNTA0XHViNzkxXHVjMmE0XHVjNWI0XHVjNzc0XHVhY2UwIFx1YzViNFx1YjVhNCBcdWIyZThcdWM1YjRcdWFjMDAgXHVjNjAxXHVjNWI0XHVjNzc4XHVjOWMwXHViMjk0IFx1YmFhOFx1Yjk3OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjAxXHVjMTIwXHVjNzc0XHViMjk0IFx1YzYwMVx1YzViNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjN2E1IFx1ZDU1OFx1YjA5OFx1YzY0MCBcdWQ1MDRcdWI3OTFcdWMyYTRcdWM1YjRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1YzdhNSBcdWQ1NThcdWIwOThcdWI5N2MgXHVjNTRjXHVhY2UwXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAsIFx1YzYwMVx1YzViNFx1Yzc3OFx1YzljMCBcdWQ1MDRcdWI3OTFcdWMyYTRcdWM1YjRcdWM3NzhcdWM5YzAgXHViYWE4XHViOTc0XHViMjk0IFx1YmIzOFx1YzdhNVx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlOFx1YzViNFx1YWMwMCBcdWM2MDFcdWM1YjQgXHViYjM4XHVjN2E1XHVjNWQwXHVjMTFjIFx1YjA5OFx1ZDBjMFx1YjBhY1x1YzczY1x1YmE3NCBcdWM3NzQgXHViMmU4XHVjNWI0XHViMjk0IFx1YzYwMVx1YzViNFx1Yzc3NFx1YWNlMCwgXHVkNTA0XHViNzkxXHVjMmE0XHVjNWI0IFx1YmIzOFx1YzdhNVx1YzVkMFx1YzExYyBcdWIwOThcdWQwYzBcdWIwYWNcdWM3M2NcdWJhNzQgXHVjNzc0IFx1YjJlOFx1YzViNFx1YjI5NCBcdWQ1MDRcdWI3OTFcdWMyYTRcdWM1YjRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwMVx1YzEyMFx1Yzc3NFx1YWMwMCBcdWI0ZTRcdWM3NDAgXHViYWE4XHViNGUwIFx1YmIzOFx1YzdhNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM2MDFcdWM1YjRcdWM3NzRcdWJhNzRcdWMxMWMgXHVkNTA0XHViNzkxXHVjMmE0XHVjNWI0XHVjNzc4IFx1YjJlOFx1YzViNFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBUICZsZTsmbmJzcDsyNSk8XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJiMzhcdWM3YTVcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyZuYnNwOzIwKSBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmIzOFx1YzdhNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1YzdhNVx1Yzc0MCBcdWIyZThcdWM1YjRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViMmU4XHVjNWI0XHViMjk0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWIyZThcdWM1YjRcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWFlMzhcdWM3NzRcdWIyOTQgMTBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3YTVcdWM3NDAgXHVjNjAxXHVjNWI0IFx1YmIzOFx1YzdhNVx1Yzc3NFx1YWNlMCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3YTVcdWM3NDAgXHVkNTA0XHViNzkxXHVjMmE0XHVjNWI0IFx1YmIzOFx1YzdhNVx1Yzc3NFx1YjJlNC4gXHViMDk4XHViYTM4XHVjOWMwIFx1YmIzOFx1YzdhNVx1Yzc0MCBcdWM1YjRcdWI1YTQgXHVjNWI4XHVjNWI0XHVjNzc4XHVjOWMwIFx1YzU0YyBcdWMyMTggXHVjNWM2XHViMjk0IFx1YmIzOFx1YzdhNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjAxXHVjNWI0IFx1YmIzOFx1YzdhNVx1YWNmYyBcdWQ1MDRcdWI3OTFcdWMyYTRcdWM1YjQgXHViYjM4XHVjN2E1XHVjNzQwIFx1Y2Q1Y1x1YjMwMCAxMDAwXHVhYzFjXHVjNzU4IFx1YjJlOFx1YzViNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWIwOThcdWJhMzhcdWM5YzAgXHViYjM4XHVjN2E1XHVjNzQwIFx1Y2Q1Y1x1YjMwMCAxMFx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3YTVcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWI5YzhcdWIyZTQgXHVjNjAxXHVjNWI0XHVjNzc0XHViYTc0XHVjMTFjIFx1ZDUwNFx1Yjc5MVx1YzJhNFx1YzViNFx1Yzc3OCBcdWIyZThcdWM1YjRcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTIxNDMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCaWxpbmd1YWwgKFNtYWxsKSIsImRlc2NyaXB0aW9uIjoiPHA+RWxsaW90JiMzOTtzIHBhcmVudHMgc3BlYWsgRnJlbmNoIGFuZCBFbmdsaXNoIHRvIGhpbSBhdCBob21lLiBIZSBoYXMgaGVhcmQgYSBsb3Qgb2Ygd29yZHMsIGJ1dCBpdCBpc24mIzM5O3QgYWx3YXlzIGNsZWFyIHRvIGhpbSB3aGljaCB3b3JkIGNvbWVzIGZyb20gd2hpY2ggbGFuZ3VhZ2UhIEVsbGlvdCBrbm93cyBvbmUgc2VudGVuY2UgdGhhdCBoZSYjMzk7cyBzdXJlIGlzIEVuZ2xpc2ggYW5kIG9uZSBzZW50ZW5jZSB0aGF0IGhlJiMzOTtzIHN1cmUgaXMgRnJlbmNoLCBhbmQgc29tZSBvdGhlciBzZW50ZW5jZXMgdGhhdCBjb3VsZCBiZSBlaXRoZXIgRW5nbGlzaCBvciBGcmVuY2guIElmIGEgd29yZCBhcHBlYXJzIGluIGFuIEVuZ2xpc2ggc2VudGVuY2UsIGl0IG11c3QgYmUgYSB3b3JkIGluIEVuZ2xpc2guIElmIGEgd29yZCBhcHBlYXJzIGluIGEgRnJlbmNoIHNlbnRlbmNlLCBpdCBtdXN0IGJlIGEgd29yZCBpbiBGcmVuY2guPFwvcD5cclxuXHJcbjxwPkNvbnNpZGVyaW5nIGFsbCB0aGUgc2VudGVuY2VzIHRoYXQgRWxsaW90IGhhcyBoZWFyZCwgd2hhdCBpcyB0aGUgbWluaW11bSBwb3NzaWJsZSBudW1iZXIgb2Ygd29yZHMgdGhhdCBoZSYjMzk7cyBoZWFyZCB0aGF0IG11c3QgYmUgd29yZHMgaW4gYm90aCBFbmdsaXNoIGFuZCBGcmVuY2g/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD48c3BhbiBzdHlsZT1cImNvbG9yOiMwMDAwMDA7IGZvbnQtZmFtaWx5OmFyaWFsLHNhbnMtc2VyaWY7IGZvbnQtc2l6ZTpzbWFsbFwiPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBnaXZlcyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMsJm5ic3A7PFwvc3Bhbj48c3Ryb25nPlQ8XC9zdHJvbmc+PHNwYW4gc3R5bGU9XCJjb2xvcjojMDAwMDAwOyBmb250LWZhbWlseTphcmlhbCxzYW5zLXNlcmlmOyBmb250LXNpemU6c21hbGxcIj4uJm5ic3A7Jm5ic3A7PFwvc3Bhbj48c3Ryb25nPlQ8XC9zdHJvbmc+PHNwYW4gc3R5bGU9XCJjb2xvcjojMDAwMDAwOyBmb250LWZhbWlseTphcmlhbCxzYW5zLXNlcmlmOyBmb250LXNpemU6c21hbGxcIj4mbmJzcDt0ZXN0IGNhc2VzIGZvbGxvdy4gRWFjaCBzdGFydHMgd2l0aCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciZuYnNwOzxcL3NwYW4+PHN0cm9uZz5OPFwvc3Ryb25nPjxzcGFuIHN0eWxlPVwiY29sb3I6IzAwMDAwMDsgZm9udC1mYW1pbHk6YXJpYWwsc2Fucy1zZXJpZjsgZm9udC1zaXplOnNtYWxsXCI+LiZuYnNwOzxcL3NwYW4+PHN0cm9uZz5OPFwvc3Ryb25nPjxzcGFuIHN0eWxlPVwiY29sb3I6IzAwMDAwMDsgZm9udC1mYW1pbHk6YXJpYWwsc2Fucy1zZXJpZjsgZm9udC1zaXplOnNtYWxsXCI+Jm5ic3A7bGluZXMgZm9sbG93LCBlYWNoIG9mIHdoaWNoIGNvbnRhaW5zIGEgc2VyaWVzIG9mIHNwYWNlLXNlcGFyYXRlZCAmcXVvdDt3b3JkcyZxdW90Oy4gRWFjaCAmcXVvdDt3b3JkJnF1b3Q7IGlzIG1hZGUgdXAgb25seSBvZiBsb3dlcmNhc2UgY2hhcmFjdGVycyBhLXouIFRoZSBmaXJzdCBvZiB0aG9zZSZuYnNwOzxcL3NwYW4+PHN0cm9uZz5OPFwvc3Ryb25nPjxzcGFuIHN0eWxlPVwiY29sb3I6IzAwMDAwMDsgZm9udC1mYW1pbHk6YXJpYWwsc2Fucy1zZXJpZjsgZm9udC1zaXplOnNtYWxsXCI+Jm5ic3A7bGluZXMgaXMgYSAmcXVvdDtzZW50ZW5jZSZxdW90OyBpbiBFbmdsaXNoLCBhbmQgdGhlIHNlY29uZCBpcyBhICZxdW90O3NlbnRlbmNlJnF1b3Q7IGluIEZyZW5jaC4gVGhlIHJlc3QgY291bGQgYmUgJnF1b3Q7c2VudGVuY2VzJnF1b3Q7IGluIGVpdGhlciBFbmdsaXNoIG9yIEZyZW5jaC4gKE5vdGUgdGhhdCB0aGUgJnF1b3Q7d29yZHMmcXVvdDsgYW5kICZxdW90O3NlbnRlbmNlcyZxdW90OyBhcmUgbm90IGd1YXJhbnRlZWQgdG8gYmUgdmFsaWQgaW4gYW55IHJlYWwgbGFuZ3VhZ2UuKTxcL3NwYW4+PFwvcD5cclxuXHJcbjxoMz5MaW1pdHM8XC9oMz5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSAmbGU7Jm5ic3A7PHN0cm9uZz5UPFwvc3Ryb25nPiZuYnNwOyZsZTsgMjUuPFwvbGk+XHJcblx0PGxpPkVhY2ggd29yZCB3aWxsIGNvbnRhaW4gbm8gbW9yZSB0aGFuIDEwIGNoYXJhY3RlcnMuPFwvbGk+XHJcblx0PGxpPlRoZSB0d28gJnF1b3Q7a25vd24mcXVvdDsgc2VudGVuY2VzIHdpbGwgY29udGFpbiBubyBtb3JlIHRoYW4gMTAwMCB3b3JkcyBlYWNoLjxcL2xpPlxyXG5cdDxsaT5UaGUgJnF1b3Q7dW5rbm93biZxdW90OyBzZW50ZW5jZXMgd2lsbCBjb250YWluIG5vIG1vcmUgdGhhbiAxMCB3b3JkcyBlYWNoLjxcL2xpPlxyXG5cdDxsaT4yICZsZTsmbmJzcDs8c3Ryb25nPk48XC9zdHJvbmc+Jm5ic3A7JmxlOyAyMC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IG9uZSBsaW5lIGNvbnRhaW5pbmcgJnF1b3Q7Q2FzZSAjeDogeSZxdW90Oywgd2hlcmUgeCBpcyB0aGUgdGVzdCBjYXNlIG51bWJlciAoc3RhcnRpbmcgZnJvbSAxKSBhbmQgeSBpcyB0aGUgbWluaW11bSBudW1iZXIgb2Ygd29yZHMgdGhhdCBFbGxpb3QgaGFzIGhlYXJkIHRoYXQgbXVzdCBiZSB3b3JkcyBpbiBib3RoIEVuZ2xpc2ggYW5kIEZyZW5jaC48XC9wPlxyXG4iLCJoaW50IjoiPHA+SW4gQ2FzZSAjMSwgRWxsaW90IGtub3dzIGZvciBzdXJlIHRoYXQgdGhlIGZpcnN0IHNlbnRlbmNlIGlzIGluIEVuZ2xpc2ggYW5kIHRoZSBzZWNvbmQgaXMgaW4gRnJlbmNoLCBzbyB0aGVyZSBpcyBubyBhbWJpZ3VpdHk7IHRoZSBvbmx5IHdvcmQgdGhhdCBtdXN0IGJlIGluIGJvdGggRW5nbGlzaCBhbmQgRnJlbmNoIGlzICZxdW90O2JhZ3VldHRlcyZxdW90Oy48YnIgXC8+XHJcbjxiciBcLz5cclxuSW4gQ2FzZSAjMiwgdGhlIGxhc3QgdHdvIHNlbnRlbmNlcyBjb3VsZCBlaXRoZXIgYmU6IEVuZ2xpc2ggRW5nbGlzaCwgRW5nbGlzaCBGcmVuY2gsIEZyZW5jaCBFbmdsaXNoLCBvciBGcmVuY2ggRnJlbmNoLiBUaGUgc2Vjb25kIG9mIHRob3NlIHBvc3NpYmlsaXRpZXMgaXMgdGhlIG9uZSB0aGF0IG1pbmltaXplcyB0aGUgbnVtYmVyIG9mIHdvcmRzIGNvbW1vbiB0byBib3RoIGxhbmd1YWdlczsgdGhhdCBzZXQgdHVybnMgb3V0IHRvIGJlIGQsIGUsIGksIGFuZCBqLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

채점

  • 예제는 채점하지 않는다.