你正在玩“僵尸粉碎机”：游戏的目标是在僵尸从墓地中冒出来时，用你可靠的僵尸粉碎机将它们粉碎。墓地被表示为一个平面的二维网格。每个僵尸会在网格上的某个 $(X, Y)$ 坐标处冒出，在原地停留 1000 毫秒 (ms)，然后消失回墓地中。同一时间，一个墓地周围最多只能有一个僵尸。

你可以在 100 毫秒内移动到当前位置周围 8 个相邻单元格中的任意一个；也就是说，你可以向北、东、南、西、西北、东北、西南和东南方向移动。即使某个单元格当前有僵尸，你也可以穿过或站在该单元格上。一旦你到达僵尸所在的单元格，就可以立即粉碎它，但一旦粉碎了一个僵尸，你的僵尸粉碎机需要 750 毫秒的冷却时间，之后才能粉碎下一个僵尸。在冷却期间，你可以自由移动。例如，在 $(0, 0)$ 处粉碎一个僵尸后：

• 到达并粉碎 $(1, 1)$ 处的僵尸需要 750 毫秒；或者
• 到达并粉碎 $(20, 20)$ 处的僵尸需要 2000 毫秒。

游戏开始时（时间 $t=0$），你位于 $(0, 0)$ 单元格。在一局游戏结束后，你想知道如果你采取最优策略，最多可以粉碎多少个僵尸。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。接下来是 $T$ 个测试用例，每个测试用例的第一行包含一个整数 $Z$，表示该关卡中僵尸的数量。

接下来的 $Z$ 行，每行包含 3 个空格分隔的整数，表示给定僵尸出现和消失的位置及时间。第 $i$ 行包含整数 $X_i, Y_i$ 和 $M_i$，其中：

• $X_i$ 是僵尸 $i$ 出现的单元格的 X 坐标。
• $Y_i$ 是僵尸 $i$ 出现的单元格的 Y 坐标。
• $M_i$ 是僵尸 $i$ 出现的时间（以毫秒为单位，从游戏开始算起）。僵尸可以被粉碎的时间区间是闭区间：如果你在 $[M_i, M_i + 1000]$ 范围内的任何时间到达该单元格，且僵尸粉碎机处于就绪状态，你就可以粉碎该单元格中的僵尸。

输出格式

对于每个测试用例，输出一行 "Case #c: d"，其中 $c$ 是用例编号（从 1 开始），$d$ 是该关卡中你能粉碎的僵尸的最大数量。

数据范围

内存限制：1GB。

时间限制：6 秒。

$1 \le T \le 100$。

$-1000 \le X_i, Y_i \le 1000$。

$0 \le M_i \le 100\,000\,000 = 10^8$。

两个僵尸永远不会在同一时间出现在同一位置。换句话说，如果一个僵尸在时间 $t$ 出现在 $(x, y)$，那么任何其他出现在 $(x, y)$ 的僵尸必须在 $(t - 1001)$ 或之前，或者在 $(t + 1001)$ 或之后出现。

子任务 1

$1 \le Z \le 8$。

子任务 2

$1 \le Z \le 100$。

样例

样例输入 1

3
4
1 0 0
-1 0 0
10 10 1000
10 -10 1000
3
1 1 0
2 2 0
3 3 0
5
10 10 1000
-10 10 1000
10 -10 1000
-10 -10 1000
20 20 2000

样例输出 1

Case #1: 3
Case #2: 2
Case #3: 2