나이트 이야기

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

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

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

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

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

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

k. m

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