Description

你正在参加一场星际超空间高尔夫比赛，并成功晋级决赛！为了确保胜利，你决定制定一个完美的策略。

在超空间高尔夫中，和传统高尔夫一样，你需要用球杆击球，使球朝你选择的方向飞行。比赛场地是一个二维平面，平面上的点代表不同的球洞。球本身也用一个点表示，你可以自由选择球的起始位置，只要不和任何球洞重合即可。

由于这是超空间高尔夫，选手可以将某些球洞对连接起来形成虫洞。每个球洞可以选择保持普通状态，或者最多与另一个球洞相连（不能自连）。虫洞是无向连接，可以双向穿越。

由于环境无摩擦，当你击球后，球会沿直线永远飞行，除非碰到球洞 $h$。当球碰到球洞 $h$ 时：

• 如果 $h$ 没有连接其他球洞，球会停止；
• 如果 $h$ 连接了另一个球洞 $h'$，球会立即从 $h'$ 飞出，并保持原来的飞行方向继续移动。

你已知所有球洞的位置。你的目标是通过一次击球，最大化触碰到的不同球洞数量。为此，你需要选择：

1. 球的起始位置
2. 球的飞行方向
3. 要连接成虫洞的球洞对（可选）

注意：

• 球不能从虫洞位置开始
• 当球穿过虫洞时，进入和穿出的两个球洞都计入总数
• 每个球洞只计一次，即使多次进入或穿出
• 如果球停在某个球洞，该球洞也会被计入

Input Format

输入第一行是测试用例数量 $T$。每个测试用例包含：

• 第一行：整数 $N$ 表示球洞数量
• 接下来 $N$ 行：每行两个整数 $X_i$ 和 $Y_i$，表示第 $i$ 个球洞的坐标

Output Format

对于每个测试用例，输出一行 Case #x: y，其中：

• $x$ 是测试用例编号（从 1 开始）
• $y$ 是在最优策略下能触碰到的最大不同球洞数量

5
2
0 0
5 5
3
0 0
5 5
5 0
5
0 0
5 5
5 0
3 2
2 4
7
0 0
1 1
2 1
3 1
8 2
11 2
14 2
1
-1000000000 1000000000

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

Hint

样例解释

样例 #1：连接两个球洞形成虫洞，可以让球穿过两个球洞。如果不连接虫洞，球碰到第一个球洞就会停止，无法触碰多个球洞。

样例 #2：连接 $(0, 0)$ 和 $(5, 5)$ 的球洞。从 $(4.9, 5)$ 水平向右击球，依次经过 $(5, 5)$ → $(0, 0)$ → $(5, 0)$ 后停止。

样例 #3：连接 $(0, 0)-(5, 0)$ 和 $(3, 2)-(5, 5)$ 两对球洞。从 $(4, -1)$ 向 $(5, 0)$ 击球，依次经过 $(5, 0)$ → $(0, 0)$ → $(5, 5)$ → $(3, 2)$。

样例 #4：连接 $(0, 0)-(1, 1)$、$(2, 1)-(11, 2)$ 和 $(8, 2)-(14, 2)$ 三对球洞。从 $(-1, 0)$ 向 $(0, 0)$ 击球，可以经过所有 7 个球洞（某些球洞会被多次经过但只计一次）。

样例 #5：只有一个球洞时，直接击球入洞即可。

数据范围

• $1 \leq T \leq 100$
• 球洞坐标范围：$-10^9 \leq X_i, Y_i \leq 10^9$
• 所有球洞坐标互不相同

测试集 1（10 分，可见评测结果）

• $1 \leq N \leq 7$

测试集 2（16 分，隐藏评测结果）

• $1 \leq N \leq 100$

翻译由 DeepSeek V3 完成