There is a UFO in the form of the disc of radius r. Currently its center is in point A and it needs to move its center to point B as soon as possible. But the tricky inhabitants of the Earth are starting to suspect something, so they have built a radar in point C with a range of R, which is able to detect a UFO, if any part of it will be in the range. Because of the special features of the UFO it cannot change its height and always maintain vertical alignment. Determine the shortest path for the UFO to reach its destination not being caught by the radar.

Input

The first line of input contains number T — the amount of test cases. Next T line consist of eight integers each x_A, y_A, x_B, y_B, x_C, y_C, r and R — the coordinates of points A, B, C and radii of the UFO and radar coverage. It is guaranteed that the UFO won't be within the radar coverage in points A and B.

Constraints

1 <= T <= 1000
-1000 <= x_A, y_A, x_B, y_B, x_C, y_C, r, R <= 1000

Output

For each test case output a real number which is the shortest UFO path with two decimals after the dot.

Example

Input:
1
0 0 8 0 4 0 1 1

Output:
9.02