질량 중심

N마리의 반딧불이 무리를 연구하고 있다. 각 반딧불이는 일정한 속력으로 직선을 따라 움직인다. 당신은 우주의 중심인 위치 (0, 0, 0)에 서 있다. 모든 반딧불이의 질량은 같으며, 반딧불이 무리의 질량 중심이 당신의 위치(원점)에 얼마나 가까워지는지 알고자 한다.

각 반딧불이의 t = 0에서의 위치와 속도를 알고 있으며, t ≥ 0에만 관심이 있다. 반딧불이의 속도는 일정하며, 서로의 몸과 당신을 통과하는 것을 포함하여 모든 공간을 자유롭게 지나갈 수 있다. 시간 t에서 N마리 반딧불이의 질량 중심 위치를 M(t)라 하자. 시간 t에서 당신의 위치와 M(t) 사이의 거리를 d(t)라 하자. d(t)의 최솟값인 $d_{min}$와, d(t) = $d_{min}$이 되는 가장 이른 시간인 $t_{min}$를 구한다.

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 입력의 모든 수는 정수이다. 1 ≤ T ≤ 100 x, y, z, vx, vy, vz의 값은 -5000 이상 5000 이하이다.

작은 데이터 세트

3 ≤ N ≤ 10

큰 데이터 세트

3 ≤ N ≤ 500

입력의 첫 번째 줄에는 테스트 케이스의 수를 나타내는 하나의 정수 T가 주어진다. 각 테스트 케이스는 반딧불이의 수를 나타내는 정수 N이 포함된 줄로 시작하며, 그 뒤에 다음 형식의 줄 N개가 주어진다.

x y z vx vy vz

각 줄은 반딧불이 하나를 나타낸다. (x, y, z)는 시간 t = 0에서의 초기 위치이고, (vx, vy, vz)는 속도이다.

각 테스트 케이스마다 다음을 출력한다.

Case #X: d_{min} t_{min}

여기서 X는 1부터 시작하는 테스트 케이스 번호이다. 절대 오차 또는 상대 오차가 최대 10^{-5}인 답은 모두 정답으로 인정된다.

N개의 점 ($x_{i}$, $y_{i}$, $z_{i}$)이 주어졌을 때, 이들의 질량 중심은 점 ($x_{c}$, $y_{c}$, $z_{c}$)이며, 그 값은 다음과 같다.

x_{c} = (x_{1} + x_{2} + ... + x_{N}) / N
y_{c} = (y_{1} + y_{2} + ... + y_{N}) / N
z_{c} = (z_{1} + z_{2} + ... + z_{N}) / N