시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 48 14 14 33.333%

문제

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

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

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

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

입력

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

각 테스트 케이스의 첫째 줄에는 문장의 개수 N이 주어진다. (2 ≤ N ≤ 200) 둘째 줄부터 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
W3sicHJvYmxlbV9pZCI6IjEyMTQ0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNjAxXHVjNWI0XHVjNjQwIFx1ZDUwNFx1Yjc5MVx1YzJhNFx1YzViNCAoTGFyZ2UpIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2MDFcdWMxMjBcdWM3NzRcdWM3NTggXHViZDgwXHViYWE4XHViMmQ4XHVjNzQwIFx1YzlkMVx1YzVkMFx1YzExYyBcdWM2MDFcdWM1YjRcdWM2NDAgXHVkNTA0XHViNzkxXHVjMmE0XHVjNWI0XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWM2MDFcdWMxMjBcdWM3NzRcdWM2NDAgXHViMzAwXHVkNjU0XHVkNTVjXHViMmU0LiBcdWM2MDFcdWMxMjBcdWM3NzRcdWIyOTQgXHViOWNlXHVjNzQwIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWI0ZTRcdWM1YzhcdWM5YzBcdWI5Y2MsIFx1YzViNFx1YjVhNCBcdWIyZThcdWM1YjRcdWFjMDAgXHVkNTA0XHViNzkxXHVjMmE0XHVjNWI0XHVjNzc0XHVhY2UwIFx1YzViNFx1YjVhNCBcdWIyZThcdWM1YjRcdWFjMDAgXHVjNjAxXHVjNWI0XHVjNzc4XHVjOWMwXHViMjk0IFx1YmFhOFx1Yjk3OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjAxXHVjMTIwXHVjNzc0XHViMjk0IFx1YzYwMVx1YzViNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjN2E1IFx1ZDU1OFx1YjA5OFx1YzY0MCBcdWQ1MDRcdWI3OTFcdWMyYTRcdWM1YjRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1YzdhNSBcdWQ1NThcdWIwOThcdWI5N2MgXHVjNTRjXHVhY2UwXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAsIFx1YzYwMVx1YzViNFx1Yzc3OFx1YzljMCBcdWQ1MDRcdWI3OTFcdWMyYTRcdWM1YjRcdWM3NzhcdWM5YzAgXHViYWE4XHViOTc0XHViMjk0IFx1YmIzOFx1YzdhNVx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlOFx1YzViNFx1YWMwMCBcdWM2MDFcdWM1YjQgXHViYjM4XHVjN2E1XHVjNWQwXHVjMTFjIFx1YjA5OFx1ZDBjMFx1YjBhY1x1YzczY1x1YmE3NCBcdWM3NzQgXHViMmU4XHVjNWI0XHViMjk0IFx1YzYwMVx1YzViNFx1Yzc3NFx1YWNlMCwgXHVkNTA0XHViNzkxXHVjMmE0XHVjNWI0IFx1YmIzOFx1YzdhNVx1YzVkMFx1YzExYyBcdWIwOThcdWQwYzBcdWIwYWNcdWM3M2NcdWJhNzQgXHVjNzc0IFx1YjJlOFx1YzViNFx1YjI5NCBcdWQ1MDRcdWI3OTFcdWMyYTRcdWM1YjRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwMVx1YzEyMFx1Yzc3NFx1YWMwMCBcdWI0ZTRcdWM3NDAgXHViYWE4XHViNGUwIFx1YmIzOFx1YzdhNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM2MDFcdWM1YjRcdWM3NzRcdWJhNzRcdWMxMWMgXHVkNTA0XHViNzkxXHVjMmE0XHVjNWI0XHVjNzc4IFx1YjJlOFx1YzViNFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBUICZsZTsmbmJzcDsyNSk8XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJiMzhcdWM3YTVcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyZuYnNwOzIwMCkgXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJiMzhcdWM3YTVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM3YTVcdWM3NDAgXHViMmU4XHVjNWI0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YjJlOFx1YzViNFx1YjI5NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViMmU4XHVjNWI0XHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVhZTM4XHVjNzc0XHViMjk0IDEwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHViYjM4XHVjN2E1XHVjNzQwIFx1YzYwMVx1YzViNCBcdWJiMzhcdWM3YTVcdWM3NzRcdWFjZTAsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHViYjM4XHVjN2E1XHVjNzQwIFx1ZDUwNFx1Yjc5MVx1YzJhNFx1YzViNCBcdWJiMzhcdWM3YTVcdWM3NzRcdWIyZTQuIFx1YjA5OFx1YmEzOFx1YzljMCBcdWJiMzhcdWM3YTVcdWM3NDAgXHVjNWI0XHViNWE0IFx1YzViOFx1YzViNFx1Yzc3OFx1YzljMCBcdWM1NGMgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWJiMzhcdWM3YTVcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwMVx1YzViNCBcdWJiMzhcdWM3YTVcdWFjZmMgXHVkNTA0XHViNzkxXHVjMmE0XHVjNWI0IFx1YmIzOFx1YzdhNVx1Yzc0MCBcdWNkNWNcdWIzMDAgMTAwMFx1YWMxY1x1Yzc1OCBcdWIyZThcdWM1YjRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHViMDk4XHViYTM4XHVjOWMwIFx1YmIzOFx1YzdhNVx1Yzc0MCBcdWNkNWNcdWIzMDAgMTBcdWFjMWNcdWM3NTggXHViYjM4XHVjN2E1XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViOWM4XHViMmU0IFx1YzYwMVx1YzViNFx1Yzc3NFx1YmE3NFx1YzExYyBcdWQ1MDRcdWI3OTFcdWMyYTRcdWM1YjRcdWM3NzggXHViMmU4XHVjNWI0XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTIxNDQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCaWxpbmd1YWwgKExhcmdlKSIsImRlc2NyaXB0aW9uIjoiPHA+RWxsaW90JiMzOTtzIHBhcmVudHMgc3BlYWsgRnJlbmNoIGFuZCBFbmdsaXNoIHRvIGhpbSBhdCBob21lLiBIZSBoYXMgaGVhcmQgYSBsb3Qgb2Ygd29yZHMsIGJ1dCBpdCBpc24mIzM5O3QgYWx3YXlzIGNsZWFyIHRvIGhpbSB3aGljaCB3b3JkIGNvbWVzIGZyb20gd2hpY2ggbGFuZ3VhZ2UhIEVsbGlvdCBrbm93cyBvbmUgc2VudGVuY2UgdGhhdCBoZSYjMzk7cyBzdXJlIGlzIEVuZ2xpc2ggYW5kIG9uZSBzZW50ZW5jZSB0aGF0IGhlJiMzOTtzIHN1cmUgaXMgRnJlbmNoLCBhbmQgc29tZSBvdGhlciBzZW50ZW5jZXMgdGhhdCBjb3VsZCBiZSBlaXRoZXIgRW5nbGlzaCBvciBGcmVuY2guIElmIGEgd29yZCBhcHBlYXJzIGluIGFuIEVuZ2xpc2ggc2VudGVuY2UsIGl0IG11c3QgYmUgYSB3b3JkIGluIEVuZ2xpc2guIElmIGEgd29yZCBhcHBlYXJzIGluIGEgRnJlbmNoIHNlbnRlbmNlLCBpdCBtdXN0IGJlIGEgd29yZCBpbiBGcmVuY2guPFwvcD5cclxuXHJcbjxwPkNvbnNpZGVyaW5nIGFsbCB0aGUgc2VudGVuY2VzIHRoYXQgRWxsaW90IGhhcyBoZWFyZCwgd2hhdCBpcyB0aGUgbWluaW11bSBwb3NzaWJsZSBudW1iZXIgb2Ygd29yZHMgdGhhdCBoZSYjMzk7cyBoZWFyZCB0aGF0IG11c3QgYmUgd29yZHMgaW4gYm90aCBFbmdsaXNoIGFuZCBGcmVuY2g/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZ2l2ZXMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLCZuYnNwO1QuJm5ic3A7Jm5ic3A7VCZuYnNwO3Rlc3QgY2FzZXMgZm9sbG93LiBFYWNoIHN0YXJ0cyB3aXRoIGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyJm5ic3A7Ti4mbmJzcDtOJm5ic3A7bGluZXMgZm9sbG93LCBlYWNoIG9mIHdoaWNoIGNvbnRhaW5zIGEgc2VyaWVzIG9mIHNwYWNlLXNlcGFyYXRlZCAmcXVvdDt3b3JkcyZxdW90Oy4gRWFjaCAmcXVvdDt3b3JkJnF1b3Q7IGlzIG1hZGUgdXAgb25seSBvZiBsb3dlcmNhc2UgY2hhcmFjdGVycyBhLXouIFRoZSBmaXJzdCBvZiB0aG9zZSZuYnNwO04mbmJzcDtsaW5lcyBpcyBhICZxdW90O3NlbnRlbmNlJnF1b3Q7IGluIEVuZ2xpc2gsIGFuZCB0aGUgc2Vjb25kIGlzIGEgJnF1b3Q7c2VudGVuY2UmcXVvdDsgaW4gRnJlbmNoLiBUaGUgcmVzdCBjb3VsZCBiZSAmcXVvdDtzZW50ZW5jZXMmcXVvdDsgaW4gZWl0aGVyIEVuZ2xpc2ggb3IgRnJlbmNoLiAoTm90ZSB0aGF0IHRoZSAmcXVvdDt3b3JkcyZxdW90OyBhbmQgJnF1b3Q7c2VudGVuY2VzJnF1b3Q7IGFyZSBub3QgZ3VhcmFudGVlZCB0byBiZSB2YWxpZCBpbiBhbnkgcmVhbCBsYW5ndWFnZS4pPFwvcD5cclxuXHJcbjxwPkxpbWl0czxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgJmxlOyZuYnNwOzxzdHJvbmc+VDxcL3N0cm9uZz4mbmJzcDsmbGU7IDI1LjxcL2xpPlxyXG5cdDxsaT5FYWNoIHdvcmQgd2lsbCBjb250YWluIG5vIG1vcmUgdGhhbiAxMCBjaGFyYWN0ZXJzLjxcL2xpPlxyXG5cdDxsaT5UaGUgdHdvICZxdW90O2tub3duJnF1b3Q7IHNlbnRlbmNlcyB3aWxsIGNvbnRhaW4gbm8gbW9yZSB0aGFuIDEwMDAgd29yZHMgZWFjaC48XC9saT5cclxuXHQ8bGk+VGhlICZxdW90O3Vua25vd24mcXVvdDsgc2VudGVuY2VzIHdpbGwgY29udGFpbiBubyBtb3JlIHRoYW4gMTAgd29yZHMgZWFjaC48XC9saT5cclxuXHQ8bGk+MiAmbGU7Jm5ic3A7PHN0cm9uZz5OPFwvc3Ryb25nPiZuYnNwOyZsZTsgMjAwLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgb25lIGxpbmUgY29udGFpbmluZyAmcXVvdDtDYXNlICN4OiB5JnF1b3Q7LCB3aGVyZSB4IGlzIHRoZSB0ZXN0IGNhc2UgbnVtYmVyIChzdGFydGluZyBmcm9tIDEpIGFuZCB5IGlzIHRoZSBtaW5pbXVtIG51bWJlciBvZiB3b3JkcyB0aGF0IEVsbGlvdCBoYXMgaGVhcmQgdGhhdCBtdXN0IGJlIHdvcmRzIGluIGJvdGggRW5nbGlzaCBhbmQgRnJlbmNoLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5JbiBDYXNlICMxLCBFbGxpb3Qga25vd3MgZm9yIHN1cmUgdGhhdCB0aGUgZmlyc3Qgc2VudGVuY2UgaXMgaW4gRW5nbGlzaCBhbmQgdGhlIHNlY29uZCBpcyBpbiBGcmVuY2gsIHNvIHRoZXJlIGlzIG5vIGFtYmlndWl0eTsgdGhlIG9ubHkgd29yZCB0aGF0IG11c3QgYmUgaW4gYm90aCBFbmdsaXNoIGFuZCBGcmVuY2ggaXMgJnF1b3Q7YmFndWV0dGVzJnF1b3Q7LjxiciBcLz5cclxuPGJyIFwvPlxyXG5JbiBDYXNlICMyLCB0aGUgbGFzdCB0d28gc2VudGVuY2VzIGNvdWxkIGVpdGhlciBiZTogRW5nbGlzaCBFbmdsaXNoLCBFbmdsaXNoIEZyZW5jaCwgRnJlbmNoIEVuZ2xpc2gsIG9yIEZyZW5jaCBGcmVuY2guIFRoZSBzZWNvbmQgb2YgdGhvc2UgcG9zc2liaWxpdGllcyBpcyB0aGUgb25lIHRoYXQgbWluaW1pemVzIHRoZSBudW1iZXIgb2Ygd29yZHMgY29tbW9uIHRvIGJvdGggbGFuZ3VhZ2VzOyB0aGF0IHNldCB0dXJucyBvdXQgdG8gYmUgZCwgZSwgaSwgYW5kIGouPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

채점 및 기타 정보

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