Given three integer points $A, B, C$ on a plane, you need to find the distance from point $C$ to the line segment $AB$. The line segment $AB$ may degenerate into a single point.

Input

Each test case contains multiple test data.

The first line of the input contains an integer $T$, representing the number of test cases. For each test case:

The input consists of a single line containing 6 integers $x_A, y_A, x_B, y_B, x_C, y_C$, describing the coordinates of the three points respectively.

Output

For each test case, output a single real number representing the shortest distance. The relative or absolute error must not exceed $10^{-9}$.

Examples

Input 1

5
0 0 1 1 2 2
0 0 0 1 1 1
0 0 0 1 2 2
0 0 0 0 1 4
-1000000000 -1000000000 1000000000 1000000000 0 0

Output 1

1.4142135624
1.0000000000
2.2360679775
4.1231056256
0.0000000000

Constraints

For all data, $1 \le T \le 10^5$, and each coordinate of the points is an integer in the range $[-10^9, 10^9]$. The coordinates of the points may coincide.