Getting Lost

BaoBao is lost on an infinite two-dimensional plane! Starting from \((a_x,a_y)\), BaoBao has to find his way to his house located at \((b_x,b_y)\). But this is not an easy task for him, as there are \(n\) round obstacles scattering on the plane. The center of the \(i\)-th obstacle, whose radius is \(r_i\), is located at \((x_i,y_i)\). BaoBao is free to move on the plane, but his route can not intersect with (but can be tangent to) any obstacle.

We say BaoBao has successfully arrived at his house, if and only if the distance between the final position of BaoBao and \((b_x,b_y)\) is not greater than \(R\), and the segment connecting the final position of BaoBao and \((b_x,b_y)\) does not intersect with (but can be tangent to) any obstacle.

BaoBao is eager to go home, so your task is to help BaoBao find the shortest route which starts from \((a_x,a_y)\) and leads to his successful arrival to his house.

Input

There are multiple test cases. The first line of the input contains an integer \(T\) (about 60), indicating the number of test cases. For each test case:

The first line contains one integer \(n\) (\(0 \le n \le 2\)), indicating the number of obstacles on the plane.

The second line contains two integers \(a_x\) and \(a_y\) (\(-10^4 \le a_x, a_y \le 10^4\)), indicating the starting point of BaoBao.

The third line contains three integers \(b_x\), \(b_y\) (\(-10^4 \le b_x, b_y \le 10^4\)) and \(R\) (\(0 \le R \le 10^4\)), indicating the position of BaoBao's house and the distance mentioned in the description.

The following \(n\) lines each contains two integers \(x_i\), \(y_i\) (\(-10^4 \le x_i, y_i \le 10^4\)) and \(r_i\) (\(0 < r_i \le 10^4\)), indicating the center and the radius of an obstacle.

It's guaranteed that both \((a_x,a_y)\) and \((b_x,b_y)\) are outside of or on the boundaries of the obstacles, and the obstacles do not contain, intersect with or be tangent to each other.

Output

For each test case output one line, indicating the shortest distance for BaoBao to arrive home. Your answer will be considered correct if and only if the absolute error or relative error of your answer is less than \(10^{-6}\).

Sample Input

2
1
10 0
0 0 2
6 0 1
0
0 10
0 0 5

Sample Output

8.209191463668802
5.000000000000000

Hint

The image above illustrates the first sample test case, where $$|AD| = 3.8729833462 \qquad |\stackrel{\frown}{DE}| = 0.4201283344 \qquad |EF| = 3.9160797831$$ so the answer is \(|AD| + |\stackrel{\frown}{DE}| + |EF| = 8.2091914637\).