Given four integer points $A, B, C, D$ on a plane, you need to find the distance between line segment $AB$ and line segment $CD$. Both line segments $AB$ and $CD$ 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 8 integers $x_A, y_A, x_B, y_B, x_C, y_C, x_D, y_D$, describing the coordinates of the four points respectively.

Output

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

Examples

Input 1

6
0 0 1 1 1 0 2 1
0 0 1 1 2 2 3 3
0 0 0 100 100 0 200 300
0 0 0 100 50 50 100 50
-1000000000 -1000000000 -1000000000 1000000000 1000000000 -1000000000 1000000000 1000000000
998 244 353 114 514 19 19 810

Output 1

0.7071067812
1.4142135624
100.0000000000
50.0000000000
2000000000.0000000000
0.0000000000

Subtasks

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.