Knight Story

There is an infinitely large chessboard. $N$ knights are placed on distinct cells of this board. In addition, $N$ cells of the board are specially marked; these are called target cells. Every target cell differs from the starting cell of every knight.

Write a program that computes the minimum total number of moves needed to move all $N$ knights onto the target cells. The knights are identical and indistinguishable, so you may freely decide which knight goes to which target cell. Several knights may occupy the same cell at the same time, but in the end each target cell must contain exactly one knight.

A knight moves in an L-shape: two cells in one direction and one cell perpendicular to it. That is, from a cell $(x, y)$ it can move to one of the eight cells $(x \pm 1, y \pm 2)$ or $(x \pm 2, y \pm 1)$.

The input consists of several test cases. The first line of each test case contains the number of knights (which equals the number of target cells) $N$. ($1 \le N \le 15$) Each of the next $N$ lines contains two integers $x$ and $y$, the starting position of a knight. Each of the following $N$ lines contains the coordinates $x$ and $y$ of a target cell. All coordinates fit in a signed 32-bit integer.

The last line of the input contains a single $0$, which marks the end of the input.

For each test case, print one line in the following format.

k. m

Here $k$ is the test case number (starting from 1) and $m$ is the minimum total number of moves needed to move all knights onto the target cells.