Migrated from Lutece 719 Space Travel

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

The year is 2014. Mankind has come a long way since that crucial day in 2013 when genius students wrote those groundbreaking programs at IDI Open. Travelling in space has become as normal as feeding your personal crocodile; something you never do more than once...

You want to do something about this, and have identified the problem with space travel to it being too time consuming. You therefore decide to write a program that finds the optimal (shortest in time) travel route between two points in three dimensional space.

This is made somewhat more complex due to the existence of worm tubes. A space traveller can enter a worm tube at any point (on it) and leave at any point. This process takes no time at all. A worm tube is modelled as a line segment in a three dimensional space.

Other than in worm tubes, travel time is proportional to the distance travelled.

Input

The first line contains $T$, the number of test cases that follow. Each test case starts with a line containing an integer $N$, the number of worm tubes in space. Then follows a line containing three integers $s_x$, $s_y$ and $s_z$, the starting point for the route you're going to find the optimal route for. Then follow a line containing the corresponding end point, $e_x$, $e_y$ and $e_z$.

After that follow $N$ lines, describing the $N$ worm tubes. Each worm tube is described by $6$ integers $sx_i$, $sy_i$, $sz_i$, $ex_i$, $ey_i$ and $ez_i$, describing the start and end point of that tube.

$0 < T \le 50$

$0 \le N \le 50$

$0 < p_x, p_y, p_z \le 1000$, for all $s$ and $e$.

The two end points of a worm tube are not equal.

Any output with a relative or absolute error of $10^{-6}$ is accepted.

Output

For each test case, output a single floating point number; the distance travelled outside of worm tubes in the optimal route.

Samples

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

1.7320508075688772
21.56720748874348

Resources

IDI Open 2013 Programming Contest