Three Circles

Time Limit: 1 Second    Memory Limit: 32768 KB

Given the positions of three circles, you want to draw them on the paper with a pen. You can start drawing at any place and move the pen arbitrarily on the paper, the pen can be lifted or lowered at any time. If the pen is lifted up, you will draw nothing. You cannot draw partial circle, that means if you start drawing a circle, you must finish it, then you can draw another one.

It takes 1 unit time to move the pen a distance of 1 unit and 0 time to lift or lower the pen.

Your task is to calculate the minimum time to draw the three circles.

Input

The input starts with a number T (T<=100) on the first line, which is the number of test cases. Each test case contains 9 real numbers in a line: x1 y1 r1 x2 y2 r2 x3 y3 r3

xi, yi(-10000 <= xi, yi <= 10000), ri(0 < ri <= 10000) is the coordinate of center and radius of the i-th circle.

Any two of the circles have no common points and it never happens that one circle is entirely inside another one.

Output

For each test case, output the minimum time in a single line, the result is to be printed accurately rounded to three decimals.

Sample Input

2
0 0 0.5 -2 0 0.5 2 0 0.5
0 0 1 -2 2 1 2 2 1

Sample Output

12.425
21.322

Submit

Source: ZOJ 3rd Anniversary Contest