스타워즈

우리 은하와 섬뜩할 정도로 닮은 머나먼 은하계의 화성 근처에서 제국군과 반란군이 목숨을 건 전투를 벌이고 있다. 반란군에는 점 ($x_{i}$, $y_{i}$, $z_{i}$)으로 간주할 N척의 함선이 있다. 각 함선에는 출력이 $p_{i}$인 수신기가 있다. 반란군은 중앙 순양함에서 모든 함선으로 메시지를 보낼 수 있어야 하지만, 자금이 빠듯하여 강력한 송신기를 마련할 여유가 없다.

순양함이 (x, y, z)에 배치되고, 다른 함선 중 하나가 ($x_{i}$, $y_{i}$, $z_{i}$)에 있으며 출력이 $p_{i}$인 수신기를 갖고 있다면, 순양함 송신기의 출력은 적어도 다음과 같아야 한다.

`

(|x_{i} - x| + |y_{i} - y| + |z_{i} - z|) / p_{i}

`

순양함 송신기에 필요한 출력을 최소화하는 순양함의 위치를 찾고, 그 출력을 출력하는 것이 과제이다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 10 0 ≤ $x_{i}$, $y_{i}$, $z_{i}$ ≤ $10^{6}$ 1 ≤ $p_{i}$ ≤ $10^{6}$

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 10

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 1000

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

각 테스트 케이스의 첫 번째 줄에는 해당 테스트 케이스의 함선 수인 정수 N이 주어진다.

이어서 N개의 줄이 주어지며, 각 줄에는 정수 $x_{i}$, $y_{i}$, $z_{i}$, $p_{i}$가 한 칸의 공백으로 구분되어 주어진다. 이들은 i번째 함선의 좌표와 수신기의 출력이다. 같은 좌표에 둘 이상의 함선이 있을 수도 있다.

각 입력 케이스에 대해 다음을 출력해야 한다.

Case #X: Y

여기서 X는 테스트 케이스 번호이고, Y는 함대의 모든 함선에 도달하기에 충분한 최소 출력이다. 상대 오차 또는 절대 오차가 최대 10^{-6}인 답은 정답으로 간주한다.

첫 번째 테스트 케이스에서 네 함선의 좌표는 각각 (0, 0, 0), (1, 2, 0), (3, 4, 0), (2, 1, 0)이고, 출력은 각각 1, 1, 1, 1이다. 좌표 (1.5, 2, 0)에 출력이 3.5인 순양함을 배치하면 모든 함선에 도달할 수 있다.

두 번째 케이스에서는 송신기 출력이 0인 순양함을 함선 바로 위에 배치할 수 있다.