不幸的是，那个男孩最终破产了。看着他离去的背影，六花对这个世界有了更多的了解——但她依然是她自己。尽管如此，她仍然坐在塔上，在低重力环境下消磨时光，感到迷茫。

她望着深邃的夜空，蓝色的圆球状地球在头顶闪耀。六花想起了她的家人、朋友和故乡。她是在梦中，还是在一个“真实”的世界里？这个中二病少女自旅程开始以来第一次感到了恐惧。

她看到一颗明亮的星星在地球周围快速穿行——也许是一个地球静止轨道空间站。她该如何到达那里？白日梦又开始了。

换句话说，六花想知道从她的位置 $s$ 到星星的位置 $t$ 所需的最短距离，同时有一个球体——地球作为障碍物阻挡在那里。它们位于三维欧几里得空间中。$s$ 和 $t$ 可能位于同一位置。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 1000$)，表示测试用例的数量。接下来是 $T$ 个测试用例。

每个测试用例包含两行。

第一行包含四个整数 $o_x, o_y, o_z, r$，分别表示球体中心 $o$ 在各维度的坐标及其半径。

第二行包含六个整数 $s_x, s_y, s_z, t_x, t_y, t_z$，分别表示起点 $s$ 和终点 $t$ 在各维度的坐标。注意 $s$ 和 $t$ 可能位于同一位置。

保证 $s$ 和 $t$ 均不在障碍物内部，且输入中每个坐标值或半径均在 $[1, 1000]$ 范围内。

输出格式

输出一个数字，表示从 $s$ 到 $t$ 在不进入球体障碍物的情况下的最短距离。如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则被视为正确。

样例

样例输入 1

2
2 1 1 1
1 1 1 3 1 1
2 1 1 1
1 2 2 3 1 1

样例输出 1

3.14159265
2.64517298