$N$ 个人（一名老师和 $N-1$ 名学生）正在进行实地考察。他们正在探索一个无限的二维单位网格草地。每个人目前都占据着其中一个单元格；同一个单元格中可能有多个人。

当需要回家时，老师和学生必须全部聚集在同一个单元格中；聚集在哪个单元格并不重要，因为他们的校车可以在任何地方接他们。学生们被教导了一种使聚集更容易的算法：

• 老师是 1 号，学生编号为 2 到 $N$。
• 一个人的动作包括移动到与当前单元格至少共享一条边或一个角的 8 个单元格之一，或者选择留在当前单元格。
• 当实地考察结束的信号响起时，老师会检查是否所有 $N$ 个人都在同一个单元格中。如果是，则无需进一步行动。否则，老师开始一个回合：
  1. 首先，老师采取一个动作，如上所述。老师可以自行决定移动到哪里（如果需要移动的话）。
  2. 然后，每个学生采取一个动作，从 2 号学生开始，依次进行到 $N$ 号学生；第 $i$ 个学生在第 $(i-1)$ 个人采取动作之前不会采取自己的动作。学生的动作是确定性的：第 $i$ 个学生必须选择能使从他们所在的单元格到第 $(i-1)$ 个人所在单元格的中心到中心距离最小的选项。这绝不会产生歧义；9 个选项中总有一个会唯一地使该距离最小化。

一旦回合结束，老师会再次检查是否所有人都处于同一个单元格中。如果不是，则开始另一个回合，依此类推，直到每个人都在同一个单元格中。

如果老师采取的策略能使回合数最少，那么这个最少回合数是多少？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$：实地考察的人数。接下来有 $N$ 行。第 $i$ 行代表第 $i$ 个人，包含两个整数 $R_i$ 和 $C_i$：第 $i$ 个人最初占据的单元格的行号和列号（在网格上）。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是如上所述所需的最少回合数。

数据范围

$1 \le T \le 100$。 时间限制：每个测试集 20 秒。 内存限制：1GB。

测试集 1（可见）

$2 \le N \le 10$。 $0 \le R_i \le 8$，对于所有 $i$。 $0 \le C_i \le 8$，对于所有 $i$。

测试集 2（隐藏）

$2 \le N \le 10^4$。 $0 \le R_i \le 10^9$，对于所有 $i$。 $0 \le C_i \le 10^9$，对于所有 $i$。

样例

输入 1

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

输出 1

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

说明

在样例 1 中，老师位于 $(3, 2)$，即第 3 行第 2 列。2 号学生位于 $(0, 2)$，3 号学生位于 $(0, 0)$。老师的一种最优策略如下：

• 回合 1：
  • 移动到 $(2, 2)$。
  • 2 号学生移动到 $(1, 2)$。
  • 3 号学生移动到 $(1, 1)$。
• 回合 2：
  • 移动到 $(1, 2)$。
  • 2 号学生留在 $(1, 2)$。
  • 3 号学生移动到 $(1, 2)$。现在每个人都在同一个单元格中。

在样例 2 中，老师和两名学生一开始就在同一个单元格中，因此不需要回合。

在样例 3 中，老师可以留在原地，所有学生将在第一回合结束时移动到老师所在的单元格。

在样例 4 中，老师应该对角线移动四次以到达 $(4, 4)$。

在样例 5 中，老师应该先移动到 $(1, 1)$；然后学生 2、3 和 4 将全部移动到 $(1, 2)$。注意，即使所有学生现在都在同一个单元格中，老师并不在，因此必须开始另一个回合。在第二回合中，老师可以移动到 $(1, 2)$ 与学生汇合，此时学生将不再移动。