Star Wars (Large)

Near the planet Mars, in a faraway galaxy eerily similar to our own, the imperial forces and the rebels are fighting to the death. The rebel army has $N$ ships, and ship $i$ sits at the point $(x_i, y_i, z_i)$ in space. Ship $i$ carries a receiver of power $p_i$. The rebels have to send messages from one central cruiser to every ship, and their finances are tight, so they cannot afford a strong transmitter.

If the cruiser is placed at $(x, y, z)$, then to reach ship $i$ the power of the cruiser's transmitter has to be at least

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

The cruiser can be placed at a position whose coordinates are not integers. Find a position that minimizes the required transmitter power, and print that power.

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

The first line of each test case contains the integer $N$, the number of ships. 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 sit at the same coordinates.

Limits

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

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

Case #X: Y

$X$ is the number of the test case, starting at 1. $Y$ is the minimal power that is enough to reach every ship of the fleet. Print $Y$ rounded to exactly six digits after the decimal point, rounding up when the seventh digit is 5 or more. No input has an answer that falls exactly halfway between two values with six decimal digits, so the rounding is determined uniquely.

In the first test case the four ships have coordinates $(0, 0, 0)$, $(1, 2, 0)$, $(3, 4, 0)$, $(2, 1, 0)$ and their receiver powers are all 1. A cruiser with power 3.5 placed at $(1.5, 2, 0)$ reaches all four ships.

In the second case the cruiser can sit right on top of the ship, so the transmitter power is 0.