Peter likes to go to school by bicycle. But going by bicycle on sidewalks is forbidden and going along roads is dangerous. That's why Peter travels only along special bicycle lanes. Fortunately Peter's home and school are in the immediate proximity of such paths. In the city where Peter lives there are only two bycycle lanes. Both lanes have the form of a circle. At the points where they cross it is possible to move from one path to the other. Peter knows the point where he enters the road and the point at which it is necessary to leave to enter the school. Peter is interested in the question: "What is the minimal distance he needs to cover along the lanes to get to school?"

Input

t – the number of test cases [t<=100], then t test cases follow.
The first 2 lines of each test case contain the description of the bicycle lanes:
x1 y1 r1 - 3 integers (x1, y1 - coordinates of the center of the 1st circle, r1 - radius of 1st circle)
x2 y2 r2 - 3 integers (x2, y2 - coordinates of the center of the 2nd circle, r2 - radius of 2nd circle)
-200 <= x1, x2, y1, y2 <= 200
0 <= r1, r2 <= 200
Next 2 lines contain the coordinates of Peter's home and school:
px1, py1 - 2 real numbers
px2, py2 - 2 real numbers

You may assume that this points lie on the circle with high accuracy (10^-8). Both points may lie on the same circle.

Output

For each test case output the minimum distance that Peter needs to go from home to get to school. The precision of the answer must be under 0.0001. If it's impossible to get to school using the bicycle lanes output -1.

Example

Input:
3
0 0 5
4 0 3
3.0 4.0
1.878679656440357 -2.121320343559643
0 0 5
4 0 3
4.0 3.0
4.0 -3.0
0 0 4
10 0 4
4.0 0.0
6.0 0.0
Output:
8.4875540166
6.4350110879
-1