Giải bài trực tuyến

Imagine a chess board that extends indefinitely in both horizontal and vertical directions. N identical knights are placed on this board, each in a different square. N different squares are specially marked, which we will call the target squares, which could be different from where the knights are initially at. We would like you to determine the minimum number of knight-steps needed so that each of the target squares is occupied by one of the knights.

As illustrated in the figure, a knight moves using the normal ”L” move (1 square in one dimension and 2 squares in the other dimension.) For this problem, it is possible for more than one knight to occupy the same square while trying to reach its final destination as long as each knight ends up in a different target square.

Input

Your program will be tested on one or more test cases. Each test case is specified using 2N +1 lines.
The first line specifies (1 ≤ N ≤ 15) which is the number of knights (or targets.) The following N lines each specifies the position of a knight by specifying two integers representing the x and y location. The remaining N lines each specifies the position of a target square again by specifying two integers representing the x and y location. All coordinates are 32-bit signed integers.
The last case is followed by a line with a single zero.

Output

For each test case, print the following line:
k. m
Where k is the test case number (starting at one,) and m is the minimum number of moves.

Example

Input:
2
3 5
6 5
5 3
7 3
0

Output:
1. 3