시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 14 2 2 40.000%

문제

There are two points $A$ and $B$ and an obstacle circle $O$ on a Cartesian plane.

Now, you need to choose a point $C$ on the boundary of $O$ and then move both points $A$ and $B$ to point $C$. While moving, the path of either point $A$ or $B$ can only go outside circle $O$ or touch its boundary.

Your goal is to minimize the total moving distance, that is, the sum of the moving distances of $A$ and $B$.

입력

The first line contains a single integer $t\ (1 \le t \le 10^5)$, the number of test cases.

Each test case is given on a single line and contains seven integers $x_1, y_1, x_2, y_2, x_3, y_3, r$, where $-10^3 \le x_1, y_1, x_2, y_2, x_3, y_3 \le 10^3$ and $1 \le r \le 10^3$. Here, $A = (x_1, y_1)$, $B = (x_2, y_2)$, and $O$ is a circle centered at $(x_3, y_3)$ with radius $r$. It is guaranteed that neither $A$ nor $B$ is strictly inside $O$.

출력

For each test case, output a single line with a single real number: the answer rounded to the third decimal place. It is guaranteed that the fourth decimal place is neither $4$ nor $5$.

예제 입력 1

3
0 0 2 2 1 1 1
0 0 2 2 1 0 1
0 0 2 2 1 -1 1

예제 출력 1

3.571
2.927
3.116