Minimum transmitter power

Near the planet Mars, in a faraway galaxy much like our own, the imperial forces and the rebels are fighting. The rebel fleet has $N$ ships. Ship $i$ sits at the point $(x_i, y_i, z_i)$ and carries a receiver of power $p_i$. The rebels need to send orders from the flagship to every ship, but their budget is tight and they cannot buy a strong transmitter.

If the flagship is placed at $(x, y, z)$, then reaching the ship at $(x_i, y_i, z_i)$ whose receiver has power $p_i$ takes a transmitter power of at least

$\frac{|x_i - x| + |y_i - y| + |z_i - z|}{p_i}$

Choose the flagship position that minimizes the transmitter power needed to reach every ship, and report that power. The flagship coordinates do not have to be integers.

The first line contains the number of test cases $T$.

The first line of each test case contains the number of ships $N$. The next $N$ lines each contain four integers $x_i$, $y_i$, $z_i$ and $p_i$ separated by single spaces. The first three are the coordinates of ship $i$ and the last one is the power of its receiver. Two or more ships may share the same coordinates.

Limits

• $1 \le T \le 10$
• $1 \le N \le 10$
• $0 \le x_i, y_i, z_i \le 10^6$
• $1 \le p_i \le 10^6$

For each test case print one line in the following format.

Case #X: Y

$X$ is the number of the test case and $Y$ is the smallest transmitter power that reaches every ship of the fleet. Round $Y$ to six digits after the decimal point and print all six digits even when they are zeros. When the discarded part is exactly one half, round up.

The flagship coordinates need not be integers. If the ships are at $(0, 0, 0)$, $(1, 2, 0)$, $(3, 4, 0)$ and $(2, 1, 0)$ and every receiver has power $1$, a flagship at $(1.5, 2, 0)$ reaches all of them with transmitter power $3.5$. With a single ship the flagship can sit on top of it, so the answer is $0$.