인터스텔라 판타지

불행히도 소년은 결국 파산하고 말았다. 멀어져 가는 그의 뒷모습을 보며 리카는 세상에 대해 더 많이 알게 되었다. 그래도 그녀는 여전히 리카이다. 그녀는 여전히 탑에 앉아 낮은 중력 속에서 시간을 보내며 길을 잃은 기분을 느꼈다.

그녀는 깊고 어두운 하늘을 올려다보았다. 그곳에는 파란 둥근 지구가 머리 위에서 빛나고 있었다. 리카는 가족과 친구, 그리고 고향을 떠올렸다. 그녀는 꿈속에 있는 것일까, 아니면 "진짜" 세계에 있는 것일까? 중2병 소녀는 여행을 시작한 뒤 처음으로 두려움을 느꼈다.

그녀는 지구 주위를 빠르게 도는 밝은 별 하나를 보았다. 아마 정지 궤도 우주 정거장일 것이다. 어떻게 하면 그곳에 갈 수 있을까? 또다시 공상이 시작되었다.

다시 말해, 리카는 자신의 위치 $s$에서 별의 위치 $t$까지 이동하는 최소 거리가 궁금하다. 구, 즉 지구가 그 자리에 장애물로 놓여 있다. 두 점은 3차원 유클리드 공간에 있다. $s$와 $t$는 같은 위치일 수도 있다.

첫째 줄에는 테스트 케이스의 수를 나타내는 정수 $T (1 \leq T \leq 1000)$가 주어진다. 그다음 $T$개의 테스트 케이스가 이어진다.

각 테스트 케이스는 두 줄로 이루어진다.

첫째 줄에는 구의 중심 $o$의 각 차원 좌표와 반지름을 나타내는 네 정수 $o_x, o_y, o_z, r$가 주어진다.

둘째 줄에는 시작점 $s$와 도착점 $t$의 각 차원 좌표를 나타내는 여섯 정수 $s_x, s_y, s_z, t_x, t_y, t_z$가 주어진다. $s$와 $t$는 같은 위치일 수도 있다.

$s$와 $t$는 모두 장애물의 내부에 있지 않으며, 입력으로 주어지는 좌표와 반지름의 각 값은 $[1, 1000]$에 속한다.

구 장애물의 내부로 들어가지 않고 $s$에서 $t$까지 이동하는 최소 거리를 출력한다. 절대 오차 또는 상대 오차가 $10^{-6}$을 넘지 않으면 정답으로 인정된다.