题目描述

$N$ people from an elementary school — one teacher and $N-1$ kids — are on a field trip. They are exploring a grassy field that is an infinite two-dimensional grid of unit cells. Each person is currently occupying one of the cells; there may be multiple people in the same cell.

When it is time to go home, the teacher and kids must all gather in one cell; it does not matter which one, since their bus can pick them up anywhere. The kids have been taught an algorithm that makes it easier to gather:

• The teacher is person number 1, and the kids are numbered 2 through $N$.
• An action taken by a person consists of either moving to one of the 8 cells sharing at least one edge or corner with that person's current cell, or choosing to remain in their current cell.
• When the signal for the end of the field trip sounds, the teacher checks to see if all $N$ people are in the same cell. If they are, no further action is necessary. Otherwise, the teacher begins a turn:
  1. First, the teacher takes an action, as described above. It is up to the teacher to decide where, if anywhere, to move.
  2. Then, each kid takes an action, starting with kid 2, and so on up to kid $N$; the $i$-th kid does not take their action until the $(i-1)$th person has taken their action. The kids' actions are deterministic: the $i$-th kid must choose the option that minimizes the center-to-center distance from their cell to the cell of the $(i-1)$th person. This is never ambiguous; one of the 9 options will uniquely minimize that distance.
• Once the turn is complete, the teacher checks again to see if all people are in the same cell. If they are not, another turn begins, and so on, until everyone is in one cell.

If the teacher makes choices that minimize the number of turns, what is that number of turns?

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each begins with one line with an integer $N$: the number of people on the field trip. Then, there are $N$ more lines. The $i$-th of these represents the $i$-th person, and has two integers $R_i$ and $C_i$: the row and column numbers (on the grid) of the cell that the $i$-th person initially occupies.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the smallest possible number of turns required, as described above.

5
3
3 2
0 2
0 0
3
2 2
2 2
2 2
9
1 1
0 0
0 1
0 2
1 0
1 2
2 0
2 1
2 2
2
8 0
0 8
4
1 0
1 3
2 2
0 2

Case #1: 2
Case #2: 0
Case #3: 1
Case #4: 4
Case #5: 2

提示

Sample Explanation

In Sample Case #1, the teacher is at $(3, 2)$ — that is, row 3 and column 2. Kid 2 is at $(0, 2)$, and Kid 3 is at $(0, 0)$. One optimal strategy for the teacher is as follows:

• Turn 1:
  • Move to $(2, 2)$.
  • Kid 2 moves to $(1, 2)$.
  • Kid 3 moves to $(1, 1)$.
• Turn 2:
  • Move to $(1, 2)$.
  • Kid 2 remains in place in $(1, 2)$.
  • Kid 3 moves to $(1, 2)$. Now everyone is in the same cell.

In Sample Case #2, the teacher and the two kids start off in the same cell, so no turns are required.

In Sample Case #3, the teacher can remain in place, and all of the kids will move to the teacher's cell by the end of the first turn.

In Sample Case #4, the teacher should move diagonally four times to reach $(4, 4)$.

In Sample Case #5, the teacher should begin by moving to $(1, 1)$; then kids $2, 3$, and $4$ will all move to $(1, 2)$. Note that even though all the kids are now in the same cell, the teacher is not, and must start another turn. On the second turn, the teacher can move to $(1, 2)$ to join the kids, and the kids will not move.

Limits

• $1 \leq T \leq 100$.

Test set 1 (4 Pts, Visible)

• $2 \leq N \leq 10$.
• $0 \leq R_i \leq 8$, for all $i$.
• $0 \leq C_i \leq 8$, for all $i$.

Test set 2 (10 Pts, Hidden)

• $2 \leq N \leq 10^4$.
• $0 \leq R_i \leq 10^9$, for all $i$.
• $0 \leq C_i \leq 10^9$, for all $i$.