The Hunter

Time limit1sMemory limit128 MB

Summary

Find the shortest rope between two points outside a circle that never enters it, straight when clear and two tangents joined by an arc otherwise.

Level: Medium5 of 10
Topics: Geometry, Math
Solved: No attempts yet

Problem

Rexxar shouts, "I will hunt you down!"

Rexxar is a legendary hunter who catches angry chickens with a harpoon tied to a rope. Rope has grown expensive lately, and that worries him.

A stone henge shaped like a cylinder of radius $R$ stands at the origin $(0, 0)$ of the plain where he hunts. It is infinitely tall and solid, so the rope cannot pass through it. The rope is spun from microfibre, so its thickness is negligible, and Rexxar can throw the harpoon along any path he likes and still hit the chicken.

Rexxar stands at $(X_1, Y_1)$ and the angry chicken sits at $(X_2, Y_2)$ . The rope lies flat on the plain and may not enter the stone henge. Find the shortest rope that connects the two points.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 1000$ ).

Each of the next $T$ lines contains five real numbers $X_1$ , $Y_1$ , $X_2$ , $Y_2$ , $R$ separated by spaces. Rexxar is at $(X_1, Y_1)$ , the angry chicken is at $(X_2, Y_2)$ , and the stone henge has radius $R$ ( $-10000 \le X_1, Y_1, X_2, Y_2 \le 10000$ , $0 < R \le 10000$ ).

Both positions lie outside the stone henge or on its boundary, so each one is at distance at least $R$ from the origin.

Output

For each test case, print the shortest rope length on its own line, rounded at the fourth decimal place and given to three decimal places.

Examples5

Example 1
Input
```
2
1 1 -1 -1 1
1 1 -1 1 1
```
Expected output
```
3.571
2.000
```
Example 2
Input
```
1
5 5 5 -5 1
```
Expected output
```
10.000
```
Example 3
Input
```
1
1 0 -1 0 1
```
Expected output
```
3.142
```
Example 4
Input
```
1
3 4 3 4 2
```
Expected output
```
0.000
```

Example 5

Input

Expected output