스타워즈 (큰 입력)

우리 은하와 이상하게 닮은 먼 은하계, 화성 근처에서 제국군과 반란군이 목숨을 걸고 싸우고 있다. 반란군의 함선은 $N$대이고, $i$번 함선은 공간의 점 $(x_i, y_i, z_i)$에 있다. $i$번 함선에는 성능이 $p_i$인 수신기가 달려 있다. 반란군은 중앙 순양함 한 대에서 모든 함선으로 통신을 보내야 하는데, 자금이 빠듯해서 강한 송신기를 살 수 없다.

순양함을 $(x, y, z)$에 두면, $i$번 함선까지 신호를 보내기 위해 순양함 송신기의 성능은 적어도 다음 값이어야 한다.

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

순양함은 좌표가 정수가 아닌 위치에도 놓을 수 있다. 송신기에 필요한 성능이 최소가 되는 순양함의 위치를 찾아 그 성능을 출력하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 함선의 수 $N$이 주어진다. 다음 $N$개 줄에는 각각 네 정수 $x_i$, $y_i$, $z_i$, $p_i$가 공백 하나로 구분되어 주어진다. 앞의 세 값은 $i$번 함선의 좌표이고, 마지막 값은 그 함선에 달린 수신기의 성능이다. 좌표가 같은 함선이 둘 이상 있을 수 있다.

제한

• $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$

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

Case #X: Y

$X$는 테스트 케이스 번호이고 1부터 시작한다. $Y$는 함대의 모든 함선에 신호를 보내기에 충분한 최소 송신기 성능이다. $Y$는 소수점 아래 여섯째 자리에서 반올림해서(일곱째 자리가 5 이상이면 올림) 소수점 아래 여섯 자리를 빠짐없이 출력한다. 정답이 소수점 아래 여섯 자리인 두 값의 정확히 중간에 놓이는 입력은 없으므로, 반올림 결과는 하나로 정해진다.

첫 번째 테스트 케이스에서 네 함선의 좌표는 $(0, 0, 0)$, $(1, 2, 0)$, $(3, 4, 0)$, $(2, 1, 0)$이고 수신기 성능은 모두 1이다. 성능이 3.5인 순양함을 $(1.5, 2, 0)$에 두면 네 함선 모두에 신호가 닿는다.

두 번째 테스트 케이스에서는 순양함을 함선과 같은 자리에 두면 되므로 송신기 성능은 0이다.