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: *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.

### Output

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

### Sample

input | output |
---|

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