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?

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: x_S, y_S, x_T, y_T, x_A, y_A, x_B, y_B, x_C, y_C, 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.

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