시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 104 12 11 24.444%

문제

프로도와 샘은 다가오는 빌보의 111번째 생일 파티를 계획하려고 한다. 그들은 중간계의 모든 호빗을 생일 파티에 초대했고, 단 한명의 예외도 없이 모두 참석하기로 했다. 호빗은 한 줄로 되어있는 매우 긴 식탁에 앉을것이다. 그러나, 프로도와 샘은 서로 대화를 하지 않으면서 파티를 계획했기 때문에, 각자 독자적으로 좌석표를 작성했다.

결국 프로도와 샘은 새로운 좌석표를 만들기로 했다. 이 때, 새로운 좌석표와 두 좌석표에서 다른 순서로 앉은 쌍의 수를 최소로 하려고 한다. 이 값을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 호빗의 수를 나타내는 정수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 2개의 줄은 각각 프로도의 좌석표와 샘의 좌석표이다. 각 좌석표는 한 줄로 이루어져 있고, N개의 서로 다른 알파벳 문자열로 이루어져 있다. 두 좌석표에 등장하는 호빗의 이름은 모두 같다. 입력의 마지막 줄에는 0이 있다. 이름은 최대 6글자이다.

출력

각 테스트 케이스에 대해서, 최종 좌석표와 프로도와 샘의 좌석표에서 서로 다른 순서로 앉은 쌍의 최소값을 출력한다.

예제 입력 1

3
Frodo Sam Bilbo
Sam Frodo Bilbo
5
A B C D E
B A D E C
0

예제 출력 1

1
3
W3sicHJvYmxlbV9pZCI6IjQ0NDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlNGNcdWJjZjRcdWM3NTggXHVjMGRkXHVjNzdjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWQ1MDRcdWI4NWNcdWIzYzRcdWM2NDAgXHVjMGQ4XHVjNzQwIFx1YjJlNFx1YWMwMFx1YzYyNFx1YjI5NCBcdWJlNGNcdWJjZjRcdWM3NTggMTExXHViYzg4XHVjOWY4IFx1YzBkZFx1Yzc3YyBcdWQzMGNcdWQyZjBcdWI5N2MgXHVhY2M0XHVkNjhkXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViNGU0XHVjNzQwIFx1YzkxMVx1YWMwNFx1YWNjNFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVkNjM4XHViZTU3XHVjNzQ0IFx1YzBkZFx1Yzc3YyBcdWQzMGNcdWQyZjBcdWM1ZDAgXHVjZDA4XHViMzAwXHVkNTg4XHVhY2UwLCBcdWIyZTggXHVkNTVjXHViYTg1XHVjNzU4IFx1YzYwOFx1YzY3OFx1YjNjNCBcdWM1YzZcdWM3NzQgXHViYWE4XHViNDUwIFx1Y2MzOFx1YzExZFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1ZDYzOFx1YmU1N1x1Yzc0MCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1YjQxOFx1YzViNFx1Yzc4OFx1YjI5NCBcdWI5ZTRcdWM2YjAgXHVhZTM0IFx1YzJkZFx1ZDBjMVx1YzVkMCBcdWM1NDlcdWM3NDRcdWFjODNcdWM3NzRcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YjA5OCwgXHVkNTA0XHViODVjXHViM2M0XHVjNjQwIFx1YzBkOFx1Yzc0MCBcdWMxMWNcdWI4NWMgXHViMzAwXHVkNjU0XHViOTdjIFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzRcdWMxMWMgXHVkMzBjXHVkMmYwXHViOTdjIFx1YWNjNFx1ZDY4ZFx1ZDU4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YWMwMVx1Yzc5MCBcdWIzYzVcdWM3OTBcdWM4MDFcdWM3M2NcdWI4NWMgXHVjODhjXHVjMTFkXHVkNDVjXHViOTdjIFx1Yzc5MVx1YzEzMVx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVhY2IwXHVhZDZkIFx1ZDUwNFx1Yjg1Y1x1YjNjNFx1YzY0MCBcdWMwZDhcdWM3NDAgXHVjMGM4XHViODVjXHVjNmI0IFx1Yzg4Y1x1YzExZFx1ZDQ1Y1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjODhjXHVjMTFkXHVkNDVjXHVjNjQwIFx1YjQ1MCBcdWM4OGNcdWMxMWRcdWQ0NWNcdWM1ZDBcdWMxMWMgXHViMmU0XHViOTc4IFx1YzIxY1x1YzExY1x1Yjg1YyBcdWM1NDlcdWM3NDAgXHVjMzBkXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkNWNcdWMxOGNcdWI4NWMgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ2MzhcdWJlNTdcdWM3NTggXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMTggTigxICZsZTsgTiAmbGU7IDEwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIDJcdWFjMWNcdWM3NTggXHVjOTA0XHVjNzQwIFx1YWMwMVx1YWMwMSBcdWQ1MDRcdWI4NWNcdWIzYzRcdWM3NTggXHVjODhjXHVjMTFkXHVkNDVjXHVjNjQwIFx1YzBkOFx1Yzc1OCBcdWM4OGNcdWMxMWRcdWQ0NWNcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWM4OGNcdWMxMWRcdWQ0NWNcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBOXHVhYzFjXHVjNzU4IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjNTRjXHVkMzBjXHViY2IzIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWI0NTAgXHVjODhjXHVjMTFkXHVkNDVjXHVjNWQwIFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCBcdWQ2MzhcdWJlNTdcdWM3NTggXHVjNzc0XHViOTg0XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWFjMTlcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI5ODRcdWM3NDAgXHVjZDVjXHViMzAwIDZcdWFlMDBcdWM3OTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWNkNWNcdWM4ODUgXHVjODhjXHVjMTFkXHVkNDVjXHVjNjQwIFx1ZDUwNFx1Yjg1Y1x1YjNjNFx1YzY0MCBcdWMwZDhcdWM3NTggXHVjODhjXHVjMTFkXHVkNDVjXHVjNWQwXHVjMTFjIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMjFjXHVjMTFjXHViODVjIFx1YzU0OVx1Yzc0MCBcdWMzMGRcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0NDQyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU2VhdGluZyBDaGFydCIsImRlc2NyaXB0aW9uIjoiPHA+QmlsYm8mIzM5O3MgYmlydGhkYXkgaXMgY29taW5nIHVwLCBhbmQgRnJvZG8gYW5kIFNhbSBhcmUgaW4gY2hhcmdlIG9mIGFsbCB0aGUgcGFydHkgcGxhbm5pbmchIFRoZXkgaGF2ZSBpbnZpdGVkIGFsbCB0aGUgaG9iYml0cyBvZiBNaWRkbGUgRWFydGggdG8gdGhlIHBhcnR5LCBhbmQgZXZlcnlvbmUgd2lsbCBiZSBzaXR0aW5nIGluIGEgc2luZ2xlIHJvdyBhdCBhbiBleHRyZW1lbHkgbG9uZyBkaW5pbmcgdGFibGUuPFwvcD5cclxuXHJcbjxwPkhvd2V2ZXIsIGR1ZSB0byBwb29yIGNvbW11bmljYXRpb24sIEZyb2RvIGFuZCBTYW0gaGF2ZSBlYWNoIGluZGVwZW5kZW50bHkgcHV0IHRvZ2V0aGVyIGEgc2VhdGluZyBjaGFydCBmb3IgYWxsIHRoZSBob2JiaXRzIGF0IHRoZSBkaW5pbmcgdGFibGUuIEhlbHAgRnJvZG8gYW5kIFNhbSBmaW5kIG91dCBob3cgc2ltaWxhciB0aGVpciBzZWF0aW5nIGNoYXJ0cyBhcmUgYnkgY291bnRpbmcgdGhlIHRvdGFsIG51bWJlciBvZiBkaXN0aW5jdCBwYWlycyBvZiBob2JiaXRzIHdobyBhcHBlYXIgaW4gZGlmZmVyZW50IG9yZGVycyBpbiB0aGUgdHdvIGNoYXJ0cy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBmaWxlIHdpbGwgY29udGFpbiBtdWx0aXBsZSB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBiZWdpbnMgd2l0aCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMCwwMDApIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiBob2JiaXRzLiBUaGUgbmV4dCB0d28gbGluZXMgcmVwcmVzZW50IEZyb2RvJiMzOTtzIGFuZCBTYW0mIzM5O3Mgc2VhdGluZyBjaGFydHMsIHJlc3BlY3RpdmVseS4gRWFjaCBzZWF0aW5nIGNoYXJ0IGlzIHNwZWNpIGVkIGFzIGEgc2luZ2xlIGxpbmUgb2YgTiB1bmlxdWUgYWxwaGFiZXRpY2FsIHN0cmluZ3M7IHRoZSBzZXQgb2Ygc3RyaW5ncyBpbiBlYWNoIGxpbmUgYXJlIGd1YXJhbnRlZWQgdG8gYmUgaWRlbnRpY2FsLiBUaGUgZW5kLW9mLWlucHV0IGlzIGRlbm90ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgdGhlIG51bWJlciAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGlucHV0IHRlc3QgY2FzZSwgb3V0cHV0IGEgc2luZ2xlIGludGVnZXIgZGVub3RpbmcsIG91dCBvZiB0aGUgTiBjaG9vc2UgMiBkaXN0aW5jdCBwYWlycyBvZiBob2JiaXRzLCBob3cgbWFueSBwYWlycyBhcHBlYXIgaW4gZGlmZmVyZW50IG9yZGVycyBpbiBGcm9kbyYjMzk7cyBhbmQgU2FtJiMzOTtzIHNlYXRpbmcgYXJyYW5nZW1lbnRzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==