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 <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

typedef double db;
db eps=1e-9;
struct point {
	db x,y;
	point() {}
	point(db x,db y):x(x),y(y) {}
	void read() { scanf("%lf%lf",&x,&y); }
	void print() { printf("%.10f %.10f\n",x,y); }
	db len() { return sqrt(x*x+y*y); }
	db len2() { return x*x+y*y; }
};
point operator + (const point &a,const point &b) { return point(a.x+b.x,a.y+b.y);}
point operator - (const point &a,const point &b) { return point(a.x-b.x,a.y-b.y);}
point operator * (const point &a,const db &b) { return point(a.x*b,a.y*b);}
point operator / (const point &a,const db &b) { return point(a.x/b,a.y/b);}
db dot(const point &a,const point &b) { return a.x*b.x+a.y*b.y; }
db det(const point &a,const point &b) { return a.x*b.y-a.y*b.x; }
struct line {
	point a,b;
	line() {}
	line(point a,point b):a(a),b(b) {}
};
point proj(const line &a,const point &b) {
	return a.a+(a.b-a.a)*dot(a.b-a.a,b-a.a)/(a.b-a.a).len2();
}
point reflect(const line &a,const point &b) {
	return proj(a,b)*2-b;
}
int sign(db x) {
	return fabs(x)<eps?0:(x>0?1:-1);
}
int relation(const line &a,const point &b) {
	int x=sign(det(a.b-a.a,b-a.a));
	if (x==1) return 0; // COUNTER_CLOCKWISE ?????¶???
	else if (x==-1) return 1; // CLOCKWISE ?????¶???
	else {
		x=sign(dot(b-a.a,a.b-a.a));
		if (x==-1) return 2; // ONLINE_BACK
		else {
			x=sign(dot(b-a.b,a.b-a.a));
			if (x==1) return 3; // ONLINE_FRONT
			else return 4; // ON_SEGMENT
		}
	}
}
bool parallel(const line &a,const line &b) { return sign(det(a.a-a.b,b.a-b.b))==0;}
bool ismiddle(const line &a,const point &b) {
	return sign(dot(b-a.a,a.b-a.a))>=0&&sign(dot(b-a.b,a.b-a.a))<=0;
}
int crossSS(const line &a,const line &b) {
	if (sign(min(b.a.x,b.b.x)-max(a.a.x,a.b.x))==1) return 0;
	if (sign(max(b.a.x,b.b.x)-min(a.a.x,a.b.x))==-1) return 0;
	if (sign(min(b.a.y,b.b.y)-max(a.a.y,a.b.y))==1) return 0;
	if (sign(max(b.a.y,b.b.y)-min(a.a.y,a.b.y))==-1) return 0;
	int d1=sign(det(a.b-a.a,b.a-a.a))*sign(det(a.b-a.a,b.b-a.a));
	int d2=sign(det(b.b-b.a,a.a-b.a))*sign(det(b.b-b.a,a.b-b.a));
	if (d1==-1&&d2==-1) return 2; // ?§??????????
	else if (d1<=0&&d2<=0) return 1; // ????§??????????
	else return 0; // ?????????
}
point crosspoint(const line &a,const line &b) {
	double a1=det(b.b-b.a,a.a-b.a),a2=det(b.b-b.a,a.b-b.a);
	return a.a*(a2/(a2-a1))-a.b*(a1/(a2-a1));
}
double distSP(const line &a,const point &b) {
	point h=proj(a,b);
	if (ismiddle(a,h)) return (b-h).len();
	else return min((b-a.a).len(),(b-a.b).len());
}
double distSS(const line &a,const line &b) {
	if (crossSS(a,b)>=1) return 0;
	else return min(min(distSP(b,a.a),distSP(b,a.b)),min(distSP(a,b.a),distSP(a,b.b)));
}

int q;
int main() {
	scanf("%d",&q);
	rep(i,0,q) {
		point p1,p2,q1,q2;
		p1.read(); p2.read(); q1.read(); q2.read();
		printf("%.10f\n",distSS(line(p1,p2),line(q1,q2)));
	}
}