ADV04D - UFO

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 xA, yA, xB, yB, xC, yC, 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 <= xA, yA, xB, yB, xC, yC, 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

Added by:Spooky
Date:2010-11-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Advancement Autumn 2010, http://sevolymp.uuuq.com/, author: Alexey Shchepin

hide comments
2011-06-15 15:43:15 blashyrkh
Can r or/and R be negative?
2010-11-27 16:28:52 :D
In my opinion a picture would be to much of a hint on this problem. I don't think that you need a hint on this one :) The geometry issue here is pretty similar to the one in ELASTIC.
2010-11-27 09:04:56 [Rampage] Blue.Mary
Can someone explain the example by a picture?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.