C. Delivery Robot
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A delivery robot is an autonomous machine designed to provide delivery services. On many campuses, such as UESTC, these robots can offer significant convenience to students.

A delivery robot typically integrates various assistance systems, such as collision avoidance systems. These systems should enable the robot to automatically avoid both static obstacles and other robots. Due to the non-immediate nature of velocity control, collision avoidance systems typically allocate a time interval $$$\Delta t$$$. If a collision is predicted to occur within $$$\Delta t$$$ at the current velocity, the system adjusts the robot's velocity accordingly, including its speed and direction.

In this problem, we simplify the collision detection model by considering the motion of two circles $$$A,B$$$ on a plane, with $$$\Delta t=1$$$. The circles' radii $$$r_A,r_B$$$, their center positions $$$P_A,P_B$$$, and their current velocities $$${\bf{v}}_A,{\bf{v}}_B$$$ are given. It is guaranteed that the circles are strictly disjoint at the start, and we assume a collision occurs when the circles intersect. With circle $$$B$$$'s velocity remaining constant, the velocity of circle $$$A$$$ may need to be adjusted to prevent a collision within $$$\Delta t=1$$$, i.e. to change $$${\bf{v}}_A$$$ into $$${\bf{v}}'_A$$$. We assume that the velocity can change instantly at the beginning of $$$\Delta t$$$ but remains constant throughout $$$\Delta t$$$. In this problem, you only need to consider the first $$$\Delta t=1$$$ from the current starting point, without considering the subsequent process.

Without an upper limit on speed, it is evident that a suitable $$${\bf{v}}'_A$$$ must exist to prevent a collision within $$$\Delta t=1$$$. Depending on the situation, different strategies can be used to select $$${\bf{v}}'_A$$$. The objective of this problem is to choose a $$${\bf{v}}'_A$$$ that minimizes the magnitude of the difference between $$${\bf{v}}_A$$$ and $$${\bf{v}}'_A$$$, i.e. $$${\bf{v}}'_A=\arg\min_{\bf{v}}\Vert {\bf{v}}_A-{\bf{v}}\Vert$$$. The magnitude of a vector $$${\bf{u}}=(x,y)$$$ is defined as $$$\Vert{\bf{u}}\Vert=\sqrt{x^2+y^2}$$$.

Input

The first line contains an integer $$$T$$$ ($$$1\le T \le 10^5$$$), indicating the number of test cases.

The first line of each test case contains five integers $$$r_A,x_{P_A},y_{P_A},x_{{\bf{v}}_A},y_{{\bf{v}}_A}$$$ ($$$0 \lt r_A\le 10^9$$$, $$$-10^9 \le x_{P_A},y_{P_A},x_{{\bf{v}}_A},y_{{\bf{v}}_A} \le 10^9$$$), where $$$P_A=(x_{P_A},y_{P_A})$$$, $$${\bf{v}}_A=(x_{{\bf{v}}_A},y_{{\bf{v}}_A})$$$.

The second line of each test case contains five integers $$$r_B,x_{P_B},y_{P_B},x_{{\bf{v}}_B},y_{{\bf{v}}_B}$$$ ($$$0 \lt r_B\le 10^9$$$, $$$-10^9 \le x_{P_B},y_{P_B},x_{{\bf{v}}_B},y_{{\bf{v}}_B} \le 10^9$$$), where $$$P_B=(x_{P_B},y_{P_B})$$$, $$${\bf{v}}_B=(x_{{\bf{v}}_B},y_{{\bf{v}}_B})$$$.

It is guaranteed that the two circles are strictly disjoint.

Output

For each test case, output the minimum magnitude of $$${\bf{v}}_A-{\bf{v}}'_A$$$, i.e.$$$\min\Vert{\bf{v}}_A-{\bf{v}}'_A\Vert$$$, in a single line. Your answer will be considered correct if its relative or absolute error does not exceed $$$10^{-6}$$$, i.e. $$$\frac{|a-b|}{\max(1,b)}\le 10^{-6}$$$ if your answer is $$$a$$$ and the correct answer is $$$b$$$.

Example
Input
3
1 1 1 3 3
3 5 5 -3 -3
1 1 1 1 1
3 5 5 0 -1
1 1 1 -1 -1
3 5 5 1 1
Output
6.0000000000
0.3944487245
0.0000000000