Worm Tube Space Travel

Time limit1sMemory limit256 MB

Summary

Travel between two points in 3D where movement along given segments is free and all other movement costs its Euclidean length, minimizing the paid distance.

Level: Medium7 of 10
Topics: Shortest path, Geometry, Graph
Solved: No attempts yet

Problem

You travel from one point to another in three dimensional space. Space holds worm tubes, and each worm tube is a line segment. A traveller can enter a worm tube at any point on it and leave it at any point on it, and that movement takes no time at all. Outside a worm tube, travel time is proportional to the distance travelled.

For each test case, find the smallest distance travelled outside worm tubes on a route from the start point to the end point.

Input

The first line contains $T$ , the number of test cases.

Each test case begins with a line containing $N$ , the number of worm tubes. The next line contains the integers $sx$ , $sy$ and $sz$ , the start point of the route. The line after that contains the integers $ex$ , $ey$ and $ez$ , the end point.

Then follow $N$ lines. The $i$ -th of them contains six integers $sx_i$ , $sy_i$ , $sz_i$ , $ex_i$ , $ey_i$ and $ez_i$ , the two end points of the $i$ -th worm tube.

$0 < T \le 50$
$0 \le N \le 50$
Every coordinate is an integer with $0 < c \le 1000$ .
The two end points of a worm tube are never equal.
The start point and the end point can be the same.

Output

For each test case, print the smallest distance travelled outside worm tubes, rounded to exactly six digits after the decimal point. Print one value per line, in input order.

Examples2

Example 1

Input

2
0
10 12 15
9 11 16
2
100 100 100
123 126 129
102 109 103 110 120 113
108 121 104 120 125 122

Expected output

1.732051
21.567207

Example 2
Input
```
1
1
1 1 1
10 1 1
1 1 1 10 1 1
```
Expected output
```
0.000000
```