시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 85 9 5 31.250%

문제

크기가 무한대인 체스판이 있다. 나이트 N개가 체스판의 서로 다른 칸에 놓여져 있다. 체스판에는 칸 N개가 특별하게 표시되어 있고, 이 칸을 목적칸이라고 부른다. 목적칸은 나이트가 처음에 있는 칸과는 다르다.

나이트 N개가 모두 목적칸으로 이동하기 위해 필요한 최소 이동 횟수를 구하는 프로그램을 작성하시오. 나이트는 모두 똑같이 생겨서, 구분할 수 없다. 또, 나이트 여러 개가 같은 칸에 동시에 있을 수 있다. 그리고, 모든 목적칸에는 나이트가 한 개씩 있어야 한다.

위의 그림은 나이트가 움직일 수 있는 방향이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 나이트의 수 (목적칸의 수) N이 주어진다. (1 ≤ N ≤ 15) 다음 N개 줄에는 나이트의 초기 위치를 나타내는 x와 y가 주어진다. 그 다음 N개 줄에는 목적칸의 좌표가 주어진다. 모든 좌표는 32비트 부호있는 정수이다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 다음을 출력한다.

k. m

k는 테스트 케이스의 번호이고, m은 최소 이동 횟수이다.

예제 입력 1

2
3 5
6 5
5 3
7 3
0

예제 출력 1

1. 3
W3sicHJvYmxlbV9pZCI6IjQ4ODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWM3NzRcdWQyYjggXHVjNzc0XHVjNTdjXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQwNmNcdWFlMzBcdWFjMDAgXHViYjM0XHVkNTVjXHViMzAwXHVjNzc4IFx1Y2NiNFx1YzJhNFx1ZDMxMFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YjA5OFx1Yzc3NFx1ZDJiOCBOXHVhYzFjXHVhYzAwIFx1Y2NiNFx1YzJhNFx1ZDMxMFx1Yzc1OCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1Y2U3OFx1YzVkMCBcdWIxOTNcdWM1ZWNcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYjRcdWMyYTRcdWQzMTBcdWM1ZDBcdWIyOTQgXHVjZTc4IE5cdWFjMWNcdWFjMDAgXHVkMmI5XHViY2M0XHVkNTU4XHVhYzhjIFx1ZDQ1Y1x1YzJkY1x1YjQxOFx1YzViNCBcdWM3ODhcdWFjZTAsIFx1Yzc3NCBcdWNlNzhcdWM3NDQgXHViYWE5XHVjODAxXHVjZTc4XHVjNzc0XHViNzdjXHVhY2UwIFx1YmQ4MFx1Yjk3OFx1YjJlNC4gXHViYWE5XHVjODAxXHVjZTc4XHVjNzQwIFx1YjA5OFx1Yzc3NFx1ZDJiOFx1YWMwMCBcdWNjOThcdWM3NGNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1Y2U3OFx1YWNmY1x1YjI5NCBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjA5OFx1Yzc3NFx1ZDJiOCBOXHVhYzFjXHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWJhYTlcdWM4MDFcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1Yzc3NFx1YjNkOSBcdWQ2OWZcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YjA5OFx1Yzc3NFx1ZDJiOFx1YjI5NCBcdWJhYThcdWI0NTAgXHViNjExXHVhYzE5XHVjNzc0IFx1YzBkZFx1YWNhOFx1YzExYywgXHVhZDZjXHViZDg0XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YjYxMCwgXHViMDk4XHVjNzc0XHVkMmI4IFx1YzVlY1x1YjdlYyBcdWFjMWNcdWFjMDAgXHVhYzE5XHVjNzQwIFx1Y2U3OFx1YzVkMCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCwgXHViYWE4XHViNGUwIFx1YmFhOVx1YzgwMVx1Y2U3OFx1YzVkMFx1YjI5NCBcdWIwOThcdWM3NzRcdWQyYjhcdWFjMDAgXHVkNTVjIFx1YWMxY1x1YzUyOSBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2tuaWdodHRhaWwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjQ2cHg7IHdpZHRoOjI0NnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHViMDk4XHVjNzc0XHVkMmI4XHVhYzAwIFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1ZDVhNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIwOThcdWM3NzRcdWQyYjhcdWM3NTggXHVjMjE4IChcdWJhYTlcdWM4MDFcdWNlNzhcdWM3NTggXHVjMjE4KSBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTUpIFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIwOThcdWM3NzRcdWQyYjhcdWM3NTggXHVjZDA4XHVhZTMwIFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgeFx1YzY0MCB5XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJhYTlcdWM4MDFcdWNlNzhcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYWE4XHViNGUwIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAzMlx1YmU0NFx1ZDJiOCBcdWJkODBcdWQ2MzhcdWM3ODhcdWIyOTQgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWIyZTRcdWM3NGNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG5rLiBtPFwvcHJlPlxyXG5cclxuPHA+a1x1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YWNlMCwgbVx1Yzc0MCBcdWNkNWNcdWMxOGMgXHVjNzc0XHViM2Q5IFx1ZDY5Zlx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0ODg2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQSBLbmlnaHRzXHUyMDE5IFRhbGUiLCJkZXNjcmlwdGlvbiI6IjxwPkltYWdpbmUgYSBjaGVzcyBib2FyZCB0aGF0IGV4dGVuZHMgaW5kZVx1ZmIwMW5pdGVseSBpbiBib3RoIGhvcml6b250YWwgYW5kIHZlcnRpY2FsIGRpcmVjdGlvbnMuIE4gaWRlbnRpY2FsIGtuaWdodHMgYXJlIHBsYWNlZCBvbiB0aGlzIGJvYXJkLCBlYWNoIGluIGEgZGlcdWZiMDBlcmVudCBzcXVhcmUuIE4gZGlcdWZiMDBlcmVudCBzcXVhcmVzIGFyZSBzcGVjaWFsbHkgbWFya2VkLCB3aGljaCB3ZSB3aWxsIGNhbGwgdGhlIHRhcmdldCBzcXVhcmVzLCB3aGljaCBjb3VsZCBiZSBkaVx1ZmIwMGVyZW50IGZyb20gd2hlcmUgdGhlIGtuaWdodHMgYXJlIGluaXRpYWxseSBhdC4gV2Ugd291bGQgbGlrZSB5b3UgdG8gZGV0ZXJtaW5lIHRoZSBtaW5pbXVtIG51bWJlciBvZiBrbmlnaHQtc3RlcHMgbmVlZGVkIHNvIHRoYXQgZWFjaCBvZiB0aGUgdGFyZ2V0IHNxdWFyZXMgaXMgb2NjdXBpZWQgYnkgb25lIG9mIHRoZSBrbmlnaHRzLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2tuaWdodHRhaWwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjQ2cHg7IHdpZHRoOjI0NnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkFzIGlsbHVzdHJhdGVkIGluIHRoZSBcdWZiMDFndXJlLCBhIGtuaWdodCBtb3ZlcyB1c2luZyB0aGUgbm9ybWFsICZyZHF1bztMJnJkcXVvOyBtb3ZlICgxIHNxdWFyZSBpbiBvbmUgZGltZW5zaW9uIGFuZCAyIHNxdWFyZXMgaW4gdGhlIG90aGVyIGRpbWVuc2lvbi4pIEZvciB0aGlzIHByb2JsZW0sIGl0IGlzIHBvc3NpYmxlIGZvciBtb3JlIHRoYW4gb25lIGtuaWdodCB0byBvY2N1cHkgdGhlIHNhbWUgc3F1YXJlIHdoaWxlIHRyeWluZyB0byByZWFjaCBpdHMgXHVmYjAxbmFsIGRlc3RpbmF0aW9uIGFzIGxvbmcgYXMgZWFjaCBrbmlnaHQgZW5kcyB1cCBpbiBhIGRpXHVmYjAwZXJlbnQgdGFyZ2V0IHNxdWFyZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSB3aWxsIGJlIHRlc3RlZCBvbiBvbmUgb3IgbW9yZSB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBpcyBzcGVjaVx1ZmIwMWVkIHVzaW5nIDJOKzEgbGluZXMuIFRoZSBcdWZiMDFyc3QgbGluZSBzcGVjaVx1ZmIwMWVzICgxICZsZTsgTiAmbGU7IDE1KSB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGtuaWdodHMgKG9yIHRhcmdldHMuKSBUaGUgZm9sbG93aW5nIE4gbGluZXMgZWFjaCBzcGVjaVx1ZmIwMWVzIHRoZSBwb3NpdGlvbiBvZiBhIGtuaWdodCBieSBzcGVjaWZ5aW5nIHR3byBpbnRlZ2VycyByZXByZXNlbnRpbmcgdGhlIHggYW5kIHkgbG9jYXRpb24uIFRoZSByZW1haW5pbmcgTiBsaW5lcyBlYWNoIHNwZWNpXHVmYjAxZXMgdGhlIHBvc2l0aW9uIG9mIGEgdGFyZ2V0IHNxdWFyZSBhZ2FpbiBieSBzcGVjaWZ5aW5nIHR3byBpbnRlZ2VycyByZXByZXNlbnRpbmcgdGhlIHggYW5kIHkgbG9jYXRpb24uIEFsbCBjb29yZGluYXRlcyBhcmUgMzItYml0IHNpZ25lZCBpbnRlZ2Vycy48XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgY2FzZSBpcyBmb2xsb3dlZCBieSBhIGxpbmUgd2l0aCBhIHNpbmdsZSB6ZXJvLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgdGhlIGZvbGxvd2luZyBsaW5lOjxcL3A+XHJcblxyXG48cHJlPmsuXHUwMDAyIG08XC9wcmU+XHJcblxyXG48cD5XaGVyZSBrIGlzIHRoZSB0ZXN0IGNhc2UgbnVtYmVyIChzdGFydGluZyBhdCBvbmUsKSBhbmQgbSBpcyB0aGUgbWluaW11bSBudW1iZXIgb2YgbW92ZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d