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<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define dbg(x...) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); }

typedef long double db;
const db eps = 1e-8;
const db pi = acosl(-1.0);

int sgn(db x) {if(fabs(x) < eps) return 0; return x < 0 ? -1 : 1;}

struct Point{
    db x, y;
    Point(){}
    Point(db x, db y) : x(x), y(y){}
    void input(){cin >> x >> y;}
    Point operator + (const Point &b) const{
        return Point(x + b.x, y + b.y);
    }
    Point operator - (const Point &b) const {
        return Point(x - b.x, y - b.y);
    }
    db operator ^ (const Point &b) const{
        return x * b.y - y * b.x;
    }
    db operator * (const Point &b) const{
        return x * b.x + y * b.y;
    }
    Point operator * (const db &k) const{
        return Point(x * k, y * k);
    }
    Point operator / (const db &k) const{
        return Point(x / k, y / k);
    }
    db len(){
        return sqrtl(x * x + y * y);
    }
    db distance(Point p) {
        return (*this-p).len();
    }
};
struct Line{
    Point s, e;
    Line(){}
    Line(Point s, Point e) : s(s), e(e){}
    void input() {s.input(); e.input();}

    int getCrossTypeofSeg(Line v){
        int d1 = sgn((e - s) ^ (v.s - s));  //v.s 在 线段的哪一侧
        int d2 = sgn((e - s) ^ (v.e - s));  //v.e 在 线段的哪一侧
        int d3 = sgn((v.e - v.s) ^ (s - v.s));  
        int d4 = sgn((v.e - v.s) ^ (e - v.s));
        if((d1^d2) == -2 && (d3^d4) == -2) return 2; // 跨立实验满足 一个是-1一个是1

        // 1. v.s在线段上 || v.e 在线段上 || s 在另外一条线段上 || e在另外一条线段上
        return (d1 == 0 &&  sgn((v.s - s) * (v.s - e)) <= 0) ||
            (d2 == 0 && sgn((v.e - s) * (v.e - e)) <= 0) ||
            (d3 == 0 && sgn((s - v.s) * (s - v.e)) <= 0) || 
            (d4 == 0 && sgn((e - v.s) * (e - v.e)) <= 0);
    }

    db getDisPointToLine(Point p) {
        return fabs(((p-s)^(e-s))/(e-s).len());
    }

    db getDisPointToSeg(Point p) {
        if(sgn((e-s) * (p-s)) < 0 || sgn((s - e) * (p - e)) < 0) return min(s.distance(p), e.distance(p));
        return getDisPointToLine(p);
    }
    db getDisSegToSeg(Line v) {
        return min(min(getDisPointToSeg(v.s), getDisPointToSeg(v.e)), min(v.getDisPointToSeg(s), v.getDisPointToSeg(e)));
    }
}l1, l2;

int main(){
#ifndef ONLINE_JUDGE
// freopen("i.in","r",stdin);
//  freopen("o.out","w",stdout);
#endif
    int T;scanf("%d", &T);
    while(T--){
        l1.input(); l2.input();
        db res = 0;
        if(l1.getCrossTypeofSeg(l2) > 0) res = 0;
        else res = l1.getDisSegToSeg(l2);
        cout << fixed << setprecision(10) << res  <<endl;
    }

    return 0;
}