블랙홀

Alice는 위험한 블랙홀이 지구를 위협하지 못하게 하려고 한다. 현재 3-D 공간에 서로 다른 점인 세 개의 블랙홀이 있다. Alice는 정확히 세 개의 격리 구를 만들 것이며, 세 구는 모두 반지름이 같아야 한다. 구들은 서로 간섭하지 않으므로 겹칠 수 있다.

Alice는 각 블랙홀이 적어도 하나의 구에 덮이도록 이 구들을 배치해야 한다. 또한 안정성을 보장하기 위해, 적어도 하나의 구에 덮이는 점들의 전체 집합은 하나의 연결된 영역을 이루어야 한다.

Alice는 이 중대한 문제를 가능한 한 적은 비용으로 해결하려고 한다. Alice가 사용할 수 있는 최소 반지름은 얼마인가?

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. 모든 i에 대해, -1000 ≤ $X_{i}$ ≤ 1000. 모든 j ≠ k에 대해, ($X_{j}$, $Y_{j}$, $Z_{j}$) ≠ ($X_{k}$, $Y_{k}$, $Z_{k}$). (두 점의 좌표가 같은 경우는 없다.)

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

모든 i에 대해, $Y_{i}$ = 0. 모든 i에 대해, $Z_{i}$ = 0.

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

모든 i에 대해, -1000 ≤ $Y_{i}$ ≤ 1000. 모든 i에 대해, -1000 ≤ $Z_{i}$ ≤ 1000.

입력은 테스트 케이스의 수를 나타내는 정수 T 하나가 있는 한 줄로 시작한다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다. 이 줄들 중 i번째 줄에는 i번째 블랙홀의 3-D 좌표를 나타내는 세 정수 $X_{i}$, $Y_{i}$, $Z_{i}$가 주어진다.

각 테스트 케이스마다 Case #x: y 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 Alice가 문제를 해결하기 위해 사용할 수 있는 최소 반지름을 나타내는 유리수이다. y의 절대 오차 또는 상대 오차가 정답의 10^{-6} 이내이면 정답으로 간주한다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 대한 설명은 FAQ을 참고한다.

마지막 두 예제 케이스는 작은 데이터 세트에 나타나지 않는다는 점에 유의한다. 예제 케이스 #1에서 사용할 수 있는 가장 작은 반지름은 1/3이다. 세 구의 중심은 (-2/3, 0, 0), (0, 0, 0), (2/3, 0, 0)이어야 한다.