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 <fstream>
#include <string>
#include <iomanip>
#include <math.h>
#include <stdbool.h>
#include <algorithm>
using namespace std;

class Point {
    public:
    double x, y;

    Point(double x = 0, double y = 0): x(x), y(y) {}

    Point operator + (Point p) { return Point(x+p.x, y+p.y); }
    Point operator - (Point p) { return Point(x-p.x, y-p.y); }
    Point operator * (double a) { return Point(a*x, a*y); }
    Point operator / (double a) { return Point(x/a, y/a); }

    double abs() {return sqrt(norm()); }
    double norm() {return x*x + y*y; }
};

typedef Point Vector;


double dot(Vector a, Vector b) {
    return a.x * b.x + a.y * b.y;
}

double cross(Vector a, Vector b) {
    return a.x*b.y - a.y*b.x;
}

Point projection(Point p1, Point p2, Point p) {
    Vector v = p2 - p1;
    Vector u = p - p1;
    Point t = p1 + v*dot(u,v)/v.norm();
    return t;
}

//2つのベクトルが平行かどうか
bool isParallel(Vector u, Vector v){
    double Cross = cross(u,v);
    bool out = (Cross==0)? true : false;
    return out;
}

//ポイントp2が線分p0p1上にいるかどうか
bool isOn(Point p0, Point p1, Point p2){
    Vector v01 = p1 - p0;
    Vector v02 = p2 - p0;
    Vector v10 = p0 - p1;
    Vector v12 = p2 - p1;

    return cross(v01,v02)==0 && dot(v01,v02)>=0 && dot(v10,v12)>=0;
}

//ポイントp2がベクトルp1-p0からみて反時計回りにいるかどうか
//CCW: 1, CW: -1, ON:0
int isCCW(Point p0, Point p1, Point p2){
    Vector v01 = p1 - p0;
    Vector v02 = p2 - p0;

    double Cross = cross(v01, v02);
    
    int out = 2;
    if (Cross>0){out = 1;}
    else if(Cross<0){out = -1;}
    else{out = 0;}

    return out;
}

bool isIntersect(Point p0, Point p1, Point p2, Point p3){
    Vector s1 = p1-p0;
    Vector s2 = p3-p2;
    bool out;
    //平行な場合
    if(isParallel(s1,s2))
    {
        out = isOn(p0,p1,p2) || isOn(p0,p1,p3) || isOn(p2,p3,p0) || isOn(p2,p3,p1);
    }
    //平行でない場合
    else     
    {
        out = ( ( isCCW(p0,p1,p2)*isCCW(p0,p1,p3) ) <= 0 ) && ( ( isCCW(p2,p3,p0)*isCCW(p2,p3,p1) ) <= 0 );
    }
    return out;
}


double ppd(Point p0, Point p1, Point p);
double dist(Point p0, Point p1, Point p);

int main(){
    #if 0
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    #endif

    int q;
    cin >> q;

    for(int i=0; i<q; i++){
        Point p0, p1, p2, p3;
        cin >> p0.x >> p0.y >> p1.x >> p1.y >> p2.x >> p2.y >> p3.x >> p3.y;

        double min = 0; 

        //交差する場合
        if(isIntersect(p0, p1, p2, p3))
        {
            min = 0;
        }
        //交差しない場合
        else
        {
            double d0 = dist(p2, p3, p0);
            double d1 = dist(p2, p3, p1);
            double d2 = dist(p0, p1, p2);
            double d3 = dist(p0, p1, p3);
            double candidate[4] = {d0, d1, d2, d3};
            min = *std::min_element(candidate, candidate + 4);
        }
        cout << setprecision(14) << min <<"\n";
    }
    
    return 0;
}

//pから直線p0p1に下ろした垂線の長さ
double ppd(Point p0, Point p1, Point p){
    Vector v = p1 - p0;
    Vector u = p - p0;

    return fabs(cross(v,u))/v.abs();
}

//pと線分p0p1の距離
double dist(Point p0, Point p1, Point p){
    if ( dot(p1-p0, p-p0) < 0 ) { return (p-p0).abs(); }
    else if ( dot(p0-p1, p-p1) < 0 ){ return (p-p1).abs(); }
    else { return ppd(p0, p1, p); }
}