题目描述

“仰望星空，看它们为你而闪烁。”—— Coldplay，《Yellow》

在遥远遥远的银河系中，有许多恒星。每颗恒星都是一个球体，具有特定的位置（在三维空间中）和半径。恒星之间可能相互重叠。

这些恒星无比美丽，令你心动，你想将它们永远留存！你打算建造两个边长相同的整数立方体，并将它们放置在空间中，使得对于每颗恒星，至少有一个立方体将其完全包含。（恒星被两个立方体的并集完全包含是不够的。）一颗恒星被一个立方体完全包含，是指恒星上没有点位于立方体之外；恰好落在立方体面上的点仍被视为在立方体内部。

立方体可以放置在空间中的任意位置，但它们的棱必须与坐标轴平行。立方体可以与恒星或彼此重叠。

请你求出能够实现目标的最小整数边长。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含一个整数 $N$，表示恒星的数量。

接下来 $N$ 行，第 $i$ 行包含四个空格分隔的整数 $X_i$、$Y_i$、$Z_i$ 和 $R_i$，分别表示第 $i$ 颗恒星的球心坐标 $(X, Y, Z)$ 以及半径 $R_i$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是上述问题中所求的最小立方体边长。

3
3
1 1 1 1
2 2 2 1
4 4 4 1
3
1 1 1 2
2 3 4 1
5 6 7 1
3
1 1 1 1
1 1 1 1
9 9 9 1

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

提示

在第一个测试用例中，一种解决方案是放置两个边长为 $3$ 的立方体，使其最小 $(x, y, z)$ 角点分别位于 $(0, 0, 0)$ 和 $(3, 3, 3)$。

在第二个测试用例中，一种解决方案是放置两个边长为 $5$ 的立方体，使其最小 $(x, y, z)$ 角点分别位于 $(-1, -1, -1)$ 和 $(1, 2, 3)$。

限制条件

$1 \le T \le 100$

对于所有 $i$，$-10^8 \le X_i \le 10^8$。

对于所有 $i$，$-10^8 \le Y_i \le 10^8$。

对于所有 $i$，$-10^8 \le Z_i \le 10^8$。

对于所有 $i$，$1 \le R_i \le 10^8$。

小数据集（测试集 1 – 可见）

$2 \le N \le 16$。

大数据集（测试集 2 – 隐藏）

$2 \le N \le 2000$。

翻译由 DeepSeek V4 Pro 完成