시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 41 12 12 34.286%

문제

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

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

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

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

입력

첫째 줄에 테스트 케이스의 개수 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+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEyMTQ0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmlsaW5ndWFsIChMYXJnZSkiLCJkZXNjcmlwdGlvbiI6IjxwPkVsbGlvdCYjMzk7cyBwYXJlbnRzIHNwZWFrIEZyZW5jaCBhbmQgRW5nbGlzaCB0byBoaW0gYXQgaG9tZS4gSGUgaGFzIGhlYXJkIGEgbG90IG9mIHdvcmRzLCBidXQgaXQgaXNuJiMzOTt0IGFsd2F5cyBjbGVhciB0byBoaW0gd2hpY2ggd29yZCBjb21lcyBmcm9tIHdoaWNoIGxhbmd1YWdlISBFbGxpb3Qga25vd3Mgb25lIHNlbnRlbmNlIHRoYXQgaGUmIzM5O3Mgc3VyZSBpcyBFbmdsaXNoIGFuZCBvbmUgc2VudGVuY2UgdGhhdCBoZSYjMzk7cyBzdXJlIGlzIEZyZW5jaCwgYW5kIHNvbWUgb3RoZXIgc2VudGVuY2VzIHRoYXQgY291bGQgYmUgZWl0aGVyIEVuZ2xpc2ggb3IgRnJlbmNoLiBJZiBhIHdvcmQgYXBwZWFycyBpbiBhbiBFbmdsaXNoIHNlbnRlbmNlLCBpdCBtdXN0IGJlIGEgd29yZCBpbiBFbmdsaXNoLiBJZiBhIHdvcmQgYXBwZWFycyBpbiBhIEZyZW5jaCBzZW50ZW5jZSwgaXQgbXVzdCBiZSBhIHdvcmQgaW4gRnJlbmNoLjxcL3A+XHJcblxyXG48cD5Db25zaWRlcmluZyBhbGwgdGhlIHNlbnRlbmNlcyB0aGF0IEVsbGlvdCBoYXMgaGVhcmQsIHdoYXQgaXMgdGhlIG1pbmltdW0gcG9zc2libGUgbnVtYmVyIG9mIHdvcmRzIHRoYXQgaGUmIzM5O3MgaGVhcmQgdGhhdCBtdXN0IGJlIHdvcmRzIGluIGJvdGggRW5nbGlzaCBhbmQgRnJlbmNoPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGdpdmVzIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywmbmJzcDtULiZuYnNwOyZuYnNwO1QmbmJzcDt0ZXN0IGNhc2VzIGZvbGxvdy4gRWFjaCBzdGFydHMgd2l0aCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciZuYnNwO04uJm5ic3A7TiZuYnNwO2xpbmVzIGZvbGxvdywgZWFjaCBvZiB3aGljaCBjb250YWlucyBhIHNlcmllcyBvZiBzcGFjZS1zZXBhcmF0ZWQgJnF1b3Q7d29yZHMmcXVvdDsuIEVhY2ggJnF1b3Q7d29yZCZxdW90OyBpcyBtYWRlIHVwIG9ubHkgb2YgbG93ZXJjYXNlIGNoYXJhY3RlcnMgYS16LiBUaGUgZmlyc3Qgb2YgdGhvc2UmbmJzcDtOJm5ic3A7bGluZXMgaXMgYSAmcXVvdDtzZW50ZW5jZSZxdW90OyBpbiBFbmdsaXNoLCBhbmQgdGhlIHNlY29uZCBpcyBhICZxdW90O3NlbnRlbmNlJnF1b3Q7IGluIEZyZW5jaC4gVGhlIHJlc3QgY291bGQgYmUgJnF1b3Q7c2VudGVuY2VzJnF1b3Q7IGluIGVpdGhlciBFbmdsaXNoIG9yIEZyZW5jaC4gKE5vdGUgdGhhdCB0aGUgJnF1b3Q7d29yZHMmcXVvdDsgYW5kICZxdW90O3NlbnRlbmNlcyZxdW90OyBhcmUgbm90IGd1YXJhbnRlZWQgdG8gYmUgdmFsaWQgaW4gYW55IHJlYWwgbGFuZ3VhZ2UuKTxcL3A+XHJcblxyXG48cD5MaW1pdHM8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xICZsZTsmbmJzcDs8c3Ryb25nPlQ8XC9zdHJvbmc+Jm5ic3A7JmxlOyAyNS48XC9saT5cclxuXHQ8bGk+RWFjaCB3b3JkIHdpbGwgY29udGFpbiBubyBtb3JlIHRoYW4gMTAgY2hhcmFjdGVycy48XC9saT5cclxuXHQ8bGk+VGhlIHR3byAmcXVvdDtrbm93biZxdW90OyBzZW50ZW5jZXMgd2lsbCBjb250YWluIG5vIG1vcmUgdGhhbiAxMDAwIHdvcmRzIGVhY2guPFwvbGk+XHJcblx0PGxpPlRoZSAmcXVvdDt1bmtub3duJnF1b3Q7IHNlbnRlbmNlcyB3aWxsIGNvbnRhaW4gbm8gbW9yZSB0aGFuIDEwIHdvcmRzIGVhY2guPFwvbGk+XHJcblx0PGxpPjIgJmxlOyZuYnNwOzxzdHJvbmc+TjxcL3N0cm9uZz4mbmJzcDsmbGU7IDIwMC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IG9uZSBsaW5lIGNvbnRhaW5pbmcgJnF1b3Q7Q2FzZSAjeDogeSZxdW90Oywgd2hlcmUgeCBpcyB0aGUgdGVzdCBjYXNlIG51bWJlciAoc3RhcnRpbmcgZnJvbSAxKSBhbmQgeSBpcyB0aGUgbWluaW11bSBudW1iZXIgb2Ygd29yZHMgdGhhdCBFbGxpb3QgaGFzIGhlYXJkIHRoYXQgbXVzdCBiZSB3b3JkcyBpbiBib3RoIEVuZ2xpc2ggYW5kIEZyZW5jaC48XC9wPlxyXG4iLCJoaW50IjoiPHA+SW4gQ2FzZSAjMSwgRWxsaW90IGtub3dzIGZvciBzdXJlIHRoYXQgdGhlIGZpcnN0IHNlbnRlbmNlIGlzIGluIEVuZ2xpc2ggYW5kIHRoZSBzZWNvbmQgaXMgaW4gRnJlbmNoLCBzbyB0aGVyZSBpcyBubyBhbWJpZ3VpdHk7IHRoZSBvbmx5IHdvcmQgdGhhdCBtdXN0IGJlIGluIGJvdGggRW5nbGlzaCBhbmQgRnJlbmNoIGlzICZxdW90O2JhZ3VldHRlcyZxdW90Oy48YnIgXC8+XHJcbjxiciBcLz5cclxuSW4gQ2FzZSAjMiwgdGhlIGxhc3QgdHdvIHNlbnRlbmNlcyBjb3VsZCBlaXRoZXIgYmU6IEVuZ2xpc2ggRW5nbGlzaCwgRW5nbGlzaCBGcmVuY2gsIEZyZW5jaCBFbmdsaXNoLCBvciBGcmVuY2ggRnJlbmNoLiBUaGUgc2Vjb25kIG9mIHRob3NlIHBvc3NpYmlsaXRpZXMgaXMgdGhlIG9uZSB0aGF0IG1pbmltaXplcyB0aGUgbnVtYmVyIG9mIHdvcmRzIGNvbW1vbiB0byBib3RoIGxhbmd1YWdlczsgdGhhdCBzZXQgdHVybnMgb3V0IHRvIGJlIGQsIGUsIGksIGFuZCBqLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

채점

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