기함의 최소 송신 출력

먼 은하의 화성 근처에서 제국군과 반란군이 싸우고 있다. 반란군 함대에는 함선 $N$대가 있고, $i$번째 함선은 점 $(x_i, y_i, z_i)$에 있으며 수신 출력이 $p_i$인 수신기가 달려 있다. 반란군은 기함에서 모든 함선으로 명령을 보내야 하지만 자금이 부족해서 강한 송신기를 사지 못한다.

기함을 $(x, y, z)$에 두면, $(x_i, y_i, z_i)$에 있고 수신 출력이 $p_i$인 함선에 명령이 닿으려면 기함의 송신 출력이 적어도 다음 값이어야 한다.

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

모든 함선에 닿는 데 필요한 송신 출력이 가장 작아지도록 기함의 위치를 정하고, 그 출력을 구하라. 기함의 좌표는 정수가 아니어도 된다.

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

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

제한

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

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

Case #X: Y

$X$는 테스트 케이스의 번호이고, $Y$는 함대의 모든 함선에 닿기에 충분한 최소 송신 출력이다. $Y$는 소수점 아래 여섯째 자리까지 반올림하고, 뒤가 0이어도 여섯 자리를 모두 적는다. 버릴 부분이 정확히 절반이면 올린다.

기함의 좌표는 정수일 필요가 없다. 함선이 $(0, 0, 0)$, $(1, 2, 0)$, $(3, 4, 0)$, $(2, 1, 0)$에 있고 수신 출력이 모두 $1$이면, 기함을 $(1.5, 2, 0)$에 두어 송신 출력 $3.5$로 모든 함선에 닿을 수 있다. 함선이 하나뿐이면 기함을 그 함선 위에 둘 수 있으므로 답은 $0$이다.