ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Contest is over

I. Pakhom and the Gully

Time limit: 1.0 second
Memory limit: 64 MB
Pakhom stands at the point S and wants to reach the point T to buy the land there. But he noticed a gully, which represents a polyline ABC. What is the length of the shortest path Pakhom should walk if he doesn't want to fall into the gully?

Input

The first line contains the number of testcases n (1 ≤ n ≤ 5000). Each of the next n lines contains one testcase. Each testcase is written as 10 space-separated integers: xS, yS, xT, yT, xA, yA, xB, yB, xC, yC, the coordinates of the points S, T, A, B, and C, respectively. All points within the test case are different. Points S and T don't belong to the polyline ABC. All numbers in test cases don't exceed 10 by absolute value.

Output

For each test case output the answer on a separate line. The answer should be precise up to 10−6.

Sample

inputoutput
```3
1 2 5 6 4 4 5 2 1 6
2 2 4 3 1 3 3 3 3 1
2 1 4 4 3 2 4 3 1 4```
```8.000000
3.650282
3.828427```
Problem Author: Petr Lezhankin
Problem Source: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009
To submit the solution for this problem go to the Problem set: 1750. Pakhom and the Gully