题目描述

"Look at the stars, look how they shine for you." - Coldplay, "Yellow"

In a galaxy far, far away, there are many stars. Each one is a sphere with a certain position (in three-dimensional space) and radius. It is possible for stars to overlap each other.

The stars are so incredibly beautiful to you that you want to capture them forever! You would like to build two cubes of the same integer edge length, and place them in space such that for each star, there is at least one cube that completely contains it. (It's not enough for a star to be completely contained by the union of the two cubes.) A star is completely contained by a cube if no point on the star is outside the cube; a point exactly on a cube face is still considered to be inside the cube.

The cubes can be placed anywhere in space, but they must be placed with their edges parallel to the coordinate axes. It is acceptable for the cubes to overlap stars or each other.

What is the minimum integer edge length that allows you to achieve this goal?

输入格式

The input starts with one line containing exactly one integer $T$, which is the number of test cases. $T$ test cases follow.

Each test case begins with a line containing an integer, $N$, representing the number of stars.

This is followed by $N$ lines. On the $i$th line, there are 4 space-separated integers, $X_i$, $Y_i$, $Z_i$ and $R_i$, indicating the $(X, Y, Z)$ coordinates of the center of the $i^{th}$ star, and the radius of the $i^{th}$ star.

输出格式

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum cube edge length that solves the problem, as described above.

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

提示

In the first test case, one solution is to place two cubes with an edge length of $3$ such that their corners with minimum $(x, y, z)$ coordinates are at $(0, 0, 0)$ and $(3, 3, 3)$.

In the second test case, one solution is to place two cubes with an edge length of $5$ such that their corners with minimum $(x, y, z)$ coordinates are at $(-1, -1, -1)$ and $(1, 2, 3)$.

Limits

$1 \le T \le 100$

$-10^8 \le X_i \le 10^8$, for all i.

$-10^8 \le Y_i \le 10^8$, for all i.

$-10^8 \le Z_i \le 10^8$, for all i.

$1 \le R_i \le 10^8$, for all i.

Small dataset (Test set 1 - Visible)

$2 \le N \le 16$.

Large dataset (Test set 2 - Hidden)

$2 \le N \le 2000$.