Let the Earth be a sphere centered at $$$(0,0,0)$$$ with a radius $$$r$$$ in 3D Euclidean space. There is a flight flying along the shortest path from the departure place to the destination place on the surface of the Earth.
As an aviation enthusiast, you have a receiver that can receive the signal from the flight with a distance no more than $$$d$$$. Note that we calculate the distance between two points by measuring the shortest path on the surface of the Earth, which is NOT the Euclidean distance in 3D Euclidean space. You need to find the minimum $$$d$$$ so that you can receive the signal from the flight at some time with the receiver in your place.
There are multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 10^4$$$) indicating the number of test cases. For each test case:
The first line contains an integer $$$r$$$ ($$$1 \le r \le 100$$$) indicating the radius of the Earth.
The second line contains three integers $$$a$$$, $$$b$$$ and $$$c$$$ ($$$-100 \le a, b, c \le 100$$$, $$$a^2 + b^2 + c^2 \gt 0$$$), indicating that your place has coordinates $$$\left( \frac{ra}{\sqrt{a^2 + b^2 + c^2}}, \frac{rb}{\sqrt{a^2 + b^2 + c^2}}, \frac{rc}{\sqrt{a^2 + b^2 + c^2}} \right)$$$.
The third line contains three integers $$$u$$$, $$$v$$$ and $$$w$$$ ($$$-100 \le u, v, w \le 100$$$, $$$u^2 + v^2 + w^2 \gt 0$$$), indicating that the departure place has coordinates $$$\left( \frac{ru}{\sqrt{u^2 + v^2 + w^2}}, \frac{rv}{\sqrt{u^2 + v^2 + w^2}}, \frac{rw}{\sqrt{u^2 + v^2 + w^2}} \right)$$$.
The fourth line contains three integers $$$x$$$, $$$y$$$ and $$$z$$$ ($$$-100 \le x, y, z \le 100$$$, $$$x^2 + y^2 + z^2 \gt 0$$$), indicating that the destination place has coordinates $$$\left( \frac{rx}{\sqrt{x^2 + y^2 + z^2}}, \frac{ry}{\sqrt{x^2 + y^2 + z^2}}, \frac{rz}{\sqrt{x^2 + y^2 + z^2}} \right)$$$.
It is guaranteed that the departure place and the destination place cannot coincide with each other and cannot be directly opposite each other on the Earth. Therefore, the shortest path from the departure place to the destination place on the surface of the Earth is uniquely determined.
For each test case, output one line containing one real number, indicating the minimum $$$d$$$ so that you can receive the signal from the flight at some time with the receiver in your place.
Your answer is acceptable if its absolute or relative error does not exceed $$$10^{-4}$$$. Formally speaking, suppose that your output is $$$a$$$ and the jury's answer is $$$b$$$, and your output is accepted if and only if $$$\frac{|a - b|}{\max(1, |b|)} \le 10^{-4}$$$.
21001 1 11 0 00 1 0100-1 -1 01 0 00 1 0
61.547970867038734110 235.619449019234492887
The following figure illustrates the first sample case, where $$$P$$$ is your place, $$$S$$$ is the departure place, and $$$T$$$ is the destination place.
