Teleportation Experiment

In this problem, you are given the coordinates of a starting point ( (x_1, y_1) ) and a destination ( (x_2, y_2) ). Additionally, there are two teleportation anchors located at ( (A_x, A_y) ) and ( (B_x, B_y) ). You may travel directly from the start to the destination, or use the teleportation system: travel from the start to one anchor, teleport instantly to the other anchor, and then continue your journey to the destination. The task is to determine the minimum travel distance. The distances between two points are computed using the Euclidean distance formula: [ \text{distance} = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} ] Consider all possible routes and output the minimum distance, rounded to six decimal places.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T) ((1 \leq T \leq 10^5)), denoting the number of test cases. Each of the following (T) lines contains eight space-separated integers: (x_1), (y_1), (x_2), (y_2), (A_x), (A_y), (B_x), and (B_y), representing the coordinates of the starting point, the destination, and the two teleportation anchors respectively.

outputFormat

For each test case, output a single line on standard output (stdout) containing the minimum travel distance. The answer for each test case must be printed with exactly six decimal places.## sample

3
0 0 10 0 3 4 7 4
0 0 1 1 2 2 3 3
-1 -1 1 1 0 2 -2 -2

10.000000
1.414214
2.828427