Problem: For given two segments s1 and s2, print the distance between them.

s1 is formed by end points p0 and p1, and s2 is formed by end points p2 and p3.

Constraints

* 1 ≤ q ≤ 1000
* -10000 ≤ xpi, ypi ≤ 10000
* p0 ≠ p1 and p2 ≠ p3.

Input

The entire input looks like:


q (the number of queries)
1st query
2nd query
...
qth query


Each query consists of integer coordinates of end points of s1 and s2 in the following format:


xp0 yp0 xp1 yp1 xp2 yp2 xp3 yp3


Output

For each query, print the distance. The output values should be in a decimal fraction with an error less than 0.00000001.

Example

Input

3
0 0 1 0 0 1 1 1
0 0 1 0 2 1 1 2
-1 0 1 0 0 1 0 -1


Output

1.0000000000
1.4142135624
0.0000000000

Solution (in CPP):

Solution:
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;

struct Point{
    double x;
    double y;
    Point (double x, double y) : x(x), y(y){}
    Point operator-(Point p){
        return Point(x - p.x, y - p.y);
    }
};
typedef Point Vector;
double dot(Vector v1, Vector v2){
    return v1.x * v2.x + v1.y * v2.y;
}
double abs_(Vector v){
    return sqrt(dot(v, v));
}
double cross(Vector v1, Vector v2){
    return v1.x * v2.y - v1.y * v2.x;
}
struct Segment{
    Point p1;
    Point p2;
    Segment(Point p1, Point p2) : p1(p1), p2(p2){}
};
bool is_inSegment(Point p, Segment s){
    double max_x = s.p1.x;
    double min_x = s.p2.x;
    if (min_x > max_x) swap(min_x, max_x);
    if (p.x < min_x || p.x > max_x) return false;
    double max_y = s.p1.y;
    double min_y = s.p2.y;
    if (min_y > max_y) swap(min_y, max_y);
// cout << min_y << " " << max_y << " " << p.y << endl;
    if (p.y < min_y || p.y > max_y) return false;
    return true;
}
bool is_intersect(Segment s1, Segment s2){
    double alpha = cross(s2.p1 - s2.p2, s1.p1 - s1.p2);
    if (fabs(alpha) < 1e-10) return false;
    double beta  = cross(s2.p1, s2.p2);
    double gamma = cross(s1.p1, s1.p2);
    double x_is = ((s1.p1.x - s1.p2.x) * beta -
                   (s2.p1.x - s2.p2.x) * gamma) / alpha;
    double y_is = ((s1.p1.y - s1.p2.y) * beta -
                   (s2.p1.y - s2.p2.y) * gamma) / alpha;
    Point p_is(x_is, y_is);
    if (!is_inSegment(p_is, s1)) return false;
    if (!is_inSegment(p_is, s2)) return false;
    return true;
}
double get_distanceSP(Segment s, Point p){
// cout << "(" << s.p1.x << "," << s.p1.y << ")";
// cout << "(" << s.p2.x << "," << s.p2.y << ")   :    ";
// cout << "(" << p.x << "," << p.y << ")" << endl;
    Vector a1 = s.p2 - s.p1;
    Vector b1 = p    - s.p1;
    if (dot(a1, b1) <= 0) return abs_(b1);
    Vector a2 = s.p1 - s.p2;
    Vector b2 = p    - s.p2;
    if (dot(a2, b2) <= 0) return abs_(b2);
    return fabs(cross(a1, b1)) / abs_(a1);
}
double get_distanceSS(Segment s1, Segment s2){
    if (is_intersect(s1, s2)) return 0;
    // cout << get_distanceSP(s1, s2.p1) << " ";
    // cout << get_distanceSP(s1, s2.p2) << " ";
    // cout << get_distanceSP(s2, s1.p1) << " ";
    // cout << get_distanceSP(s2, s1.p2) << endl;
    return min(min(get_distanceSP(s1, s2.p1), get_distanceSP(s1, s2.p2)),
               min(get_distanceSP(s2, s1.p1), get_distanceSP(s2, s1.p2)));
}
int main(){
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int x_p0, y_p0, x_p1, y_p1, x_p2, y_p2, x_p3, y_p3;
        cin >> x_p0 >> y_p0 >> x_p1 >> y_p1;
        cin >> x_p2 >> y_p2 >> x_p3 >> y_p3;
        Segment s1(Point(x_p0, y_p0), Point(x_p1, y_p1));
        Segment s2(Point(x_p2, y_p2), Point(x_p3, y_p3));
        double distance = get_distanceSS(s1, s2);
        cout << fixed << setprecision(10);
        cout << distance << endl;
    }
    return 0;
}