P16616 [GKS 2017 #A] Two Cubes

“仰望星空，看它们为你而闪烁。”—— 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$ 的立方体，使其最小 $(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 完成