반딧불이 무리의 질량 중심

반딧불이 $N$마리로 이루어진 무리를 관찰한다. 반딧불이는 저마다 일정한 속도로 직선을 따라 움직인다. 나는 공간의 원점 $(0, 0, 0)$에 서 있다. 반딧불이의 질량은 모두 같고, 무리의 중심이 나에게 얼마나 가까이 오는지 알고 싶다.

시각 $t = 0$에서 반딧불이 각각의 위치와 속도를 알고 있으며, $t \ge 0$인 시각만 생각한다. 속도는 변하지 않고, 반딧불이는 다른 반딧불이와 나를 포함해 무엇이든 그대로 통과한다. 시각 $t$에서 반딧불이 $N$마리의 질량 중심을 $M(t)$, 원점과 $M(t)$ 사이의 거리를 $d(t)$라고 하자. $t \ge 0$에서 $d(t)$의 최솟값 $d_{\min}$과, $d(t) = d_{\min}$이 되는 가장 이른 시각 $t_{\min}$을 구한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 반딧불이의 수 $N$이 주어지고, 이어서 다음 형식의 줄이 $N$개 주어진다.

x y z vx vy vz

각 줄은 반딧불이 한 마리를 나타낸다. $(x, y, z)$는 시각 $t = 0$에서의 위치이고, $(v_x, v_y, v_z)$는 속도이다.

제한

• 입력에 주어지는 수는 모두 정수이다.
• $1 \le T \le 100$
• $3 \le N \le 500$
• $-5000 \le x, y, z, v_x, v_y, v_z \le 5000$

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

Case #X: dmin tmin

$X$는 1부터 시작하는 테스트 케이스 번호이다. $d_{\min}$을 먼저 쓰고 공백 한 칸을 둔 다음 $t_{\min}$을 쓴다. 두 값 모두 소수점 아래 여덟 자리까지 반올림해 여덟 자리를 빠짐없이 출력하고, 정확히 절반인 값은 올린다. 반올림 결과가 정확해야 하는데 $t_{\min}$은 $10^6$보다 커질 수 있으므로, 배정밀도 부동소수점만 쓰면 자릿수가 모자랄 수 있다.

$N$개의 점 $(x_i, y_i, z_i)$의 질량 중심은 다음 점 $(x_c, y_c, z_c)$이다.

xc = (x1 + x2 + ... + xN) / N
yc = (y1 + y2 + ... + yN) / N
zc = (z1 + z2 + ... + zN) / N