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;
#define E 1e-18
#define ll long long
#define int long long
#define db double
#define For(i,j,k) for(int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for(int i=(int)(j);i>=(int)(k);i--)
inline ll read(){
	ll x=0;char ch=getchar();bool f=0;
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=1;
	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return f?-x:x;
}
void write(ll x){
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);putchar(x%10+'0');
}
void writeln(ll x){write(x);puts("");}
void writep(ll x){write(x);putchar(' ');}

int const N=1e5+3;
int top,n,m,cnt,sta[N];
struct point{
	db x,y;
    point operator - (point A) const{return (point){x-A.x,y-A.y};}
    point operator + (point A) const{return (point){x+A.x,y+A.y};}
    void print(){printf("%.10lf %.10lf\n",x,y);}
}A,B,C,D,c[N],p1[N],p2[N];

point operator *(db x,point A){return (point){x*A.x,x*A.y};}
db CJ(point A,point B){return A.x*B.y-B.x*A.y;}//叉积 
db DJ(point A,point B){return A.x*B.x+A.y*B.y;}//点积 
db dis(point A){return sqrt(A.x*A.x+A.y*A.y);}//向量长度 
bool cmp(point A,point B){return (CJ(A,B)>0 || CJ(A,B)==0 && dis(A)<dis(B));}//按极角排序 
point CGL_1_A(point A,point B,point C){//点在直线上的投影点
	db d=dis(B-A);
	return (A+(DJ(C-A,B-A)/d/d*(B-A)));
}
point CGL_1_B(point A,point B,point C){//点关于直线的对称点
	point P=CGL_1_A(A,B,C);
	return (C+2*(P-C));
}
int CGL_1_C(point A,point B,point C){//向量的位置关系(向量AC和向量AB) 
    if (CJ(B-A,C-A)>0) return 1;//逆时针 
    if (CJ(B-A,C-A)<0) return 2;//顺时针 
    if (DJ(C-A,B-A)<0) return 3;//方向相反
	if (dis(C-A)>dis(B-A)) return 4;//方向相同 AC>AB
	if (dis(C-A)<=dis(B-A)) return 5;//方向相同 AB>AC
}
int CGL_2_A(point A,point B,point C,point D){//判断直线平行、垂直
	if (CJ(B-A,D-C)==0) return 2;//平行 
	if (DJ(B-A,D-C)==0) return 1;//垂直 
	return 0;//相交 
}
int CGL_2_B(point A,point B,point C,point D){//判断线段是否有交
	if (min(A.x,B.x)>max(C.x,D.x) || min(C.x,D.x)>max(A.x,B.x) || min(A.y,B.y)>max(C.y,D.y) || min(C.y,D.y)>max(A.y,B.y)) return 0;//快速排斥实验(两个矩形是否相交)
	return CJ(B-A,C-A)*CJ(B-A,D-A)<=0 && CJ(D-C,A-C)*CJ(D-C,B-C)<=0;//跨立实验
}
point CGL_2_C(point A,point B,point C,point D){//求直线交点
	point p1=CGL_1_A(A,B,C),p2=CGL_1_A(A,B,D);//求C、D在AB上的投影点 
	db d1=dis(C-p1),d2=dis(D-p2);//三角形的相似比 
	if (CJ(B-A,C-A)*CJ(B-A,D-A)<0) return (C+(d1/(d1+d2)*(D-C)));
	else if (d1<d2) return (D+d2/(d2-d1+E)*(C-D));
	else return (C+d1/(d1-d2+E)*(D-C));
}
db Distance(point A,point B,point C){//点到线段的距离 
	point P=CGL_1_A(A,B,C);//C在AB上的投影点 
	if (P.x>=min(A.x,B.x) && P.x<=max(A.x,B.x) && P.y>=min(A.y,B.y) && P.y<=max(A.y,B.y)) return dis(P-C);//投影点在线段上 
	return min(dis(A-C),dis(B-C));//两个端点到C的最小值 
}
db CGL_2_D(point A,point B,point C,point D){//线段到线段的距离
	point P=CGL_2_C(A,B,C,D);//求直线交点 
	if (P.x>=min(A.x,B.x) && P.x<=max(A.x,B.x) && P.y>=min(A.y,B.y) && P.y<=max(A.y,B.y) && P.x>=min(C.x,D.x) && P.x<=max(C.x,D.x) && P.y>=min(C.y,D.y) && P.y<=max(C.y,D.y)) return 0;//线段有交点 
	return min(Distance(A,B,C),min(Distance(A,B,D),min(Distance(C,D,A),Distance(C,D,B))));
}

signed main(){
	for (int q=read();q;q--){
		scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y,&C.x,&C.y,&D.x,&D.y);
		printf("%.10lf\n",(CGL_2_D(A,B,C,D)));
	}
	return 0;
}