F. Five Steiner
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

After reading the paper Steiner minimal trees on sets of four points, one has decided to make things a bit harder. Why not five points instead?

You are given $$$5$$$ points with integer coordinates on the plane. The distance between two points is defined by the Euclidean distance.

Please find the sum of distances of the minimum weight$$$^\dagger$$$ steiner tree$$$^\ddagger$$$ of the given points.

$$$^\dagger$$$ The weight of a tree is defined by the sum of distances between all pairs of points connected by edges.

$$$^\ddagger$$$ A steiner tree is defined as a tree spanning the given points, possibly containing some arbitrary number of points added to the point set. The added points need not have integer coordinates.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$). The description of the test cases follows.

Each test case consists of five lines, containing the following input.

  1. Two integers $$$x_a$$$ and $$$y_a$$$, the coordinates of the first point $$$A$$$. ($$$-10^5 \le x_a,y_a \le 10^5$$$)
  2. Two integers $$$x_b$$$ and $$$y_b$$$, the coordinates of the second point $$$B$$$. ($$$-10^5 \le x_b,y_b \le 10^5$$$)
  3. Two integers $$$x_c$$$ and $$$y_c$$$, the coordinates of the third point $$$C$$$. ($$$-10^5 \le x_c,y_c \le 10^5$$$)
  4. Two integers $$$x_d$$$ and $$$y_d$$$, the coordinates of the fourth point $$$D$$$. ($$$-10^5 \le x_d,y_d \le 10^5$$$)
  5. Two integers $$$x_e$$$ and $$$y_e$$$, the coordinates of the fifth point $$$E$$$. ($$$-10^5 \le x_e,y_e \le 10^5$$$)
Output

For each test case, print the sum of distances of the minimum steiner tree of the given points on one line.

Your output will be accepted if the absolute or relative error does not exceed $$$10^{-5}$$$.

Example
Input
2
-2 -1
-1 1
0 -1
1 1
2 -1
0 2
3 1
-3 1
-1 -2
1 -2
Output
7.464101
11.332503