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>
#define eps (1e-10)
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 norm(){return x*x+y*y;}
	double ABS(){return sqrt(norm());} //俩点间的距离
};
struct Segment
{
	Point p1,p2;
	Segment(){}
	Segment(Point _p1,Point _p2):p1(_p1),p2(_p2){}
};

double dot(Point a,Point b)//求内积 就是向量a*b
{
	return a.x*b.x+a.y*b.y;
}
//外积的值为a与b向量构成的平行四边形面积的值
double cross(Point a,Point b)//求外积
{
	return a.x*b.y-a.y*b.x;
}


//判断是否正交 向量内积：a*b=|a||b|*cos(Y) 当cos为0时正交(90,-90垂直)
//a*b=a.x*b.x+a.y*b.y;
bool solve1(Point a,Point b)//是否正交
{
	double f=a.x*b.x+a.y*b.y;
	if(fabs(f-0.0)<eps) return true;
	else return false;
}
//判断是否平行  向量外积：|a*b|=|a||b|sin(Y) 当sin为0时平行(180,0平行)
//|a*b|=|a|*|b|*sin(Y)
bool solve2(Point a,Point b)//是否平行
{
	double f=a.x*b.y-a.y*b.x;
	if(fabs(f-0.0)<eps) return true;
	else return false;
}

/*
求垂足x：对于给定的三点p1,p2,p从点p向通过p1,p2的直线引一条垂线
base=p2-p1;
hypo=p-p1;
 x=s.p1+base*(hypo*base/|base|^2); hypo*base 可以用向量内积求
*/
Point solve3(Segment s,Point p)//求投影点
{
	Point base=s.p2-s.p1;
	double r=dot(p-s.p1,base)/base.norm();
	return s.p1+base*r;
}
/*
求投影点x：对于给定的三点p1,p2,p从点p向通过p1,p2的直线为对称轴与点p
成线对称点为x
通过求solve3的垂足延长一倍就可以求x
*/
Point solve4(Segment s,Point p)//求映象
{
	return p+(solve3(s,p)-p)*2.0;
}

/*
Point a=p1-p0;
Point b=p2-p0;
1.外积大小cross(a,b)为正时,可确定b在a的逆时针方向
	sin(Y)（Y在0-180）所以是正数
2. 外积大小cross(a,b)为负时,可确定b在a的顺时针方向
3.（1,2）不符合 表示p2在直线p0p1上(注意是直线),cos(Y)大于90或小于-90
	度时为负，因此a与b的内积dot(a,b)负时，可确定p2位于线段p0p1后方
	即p2->p0->p1
4.不是3时，有俩种p0->p1-p2或者p0->p2->p1如果b的大小大于a的大小，即为
	p0->p1->p2;
5.不符合4，可以确定p2位于线段p0p1上
*/
int ccw(Point p0,Point p1,Point p2)//判断三个点相对位置
{
	Point a=p1-p0;
	Point b=p2-p0;
	if(cross(a,b)>eps) return 1;//p0,p1,p2成逆时针方向
	if(cross(a,b)<-eps) return -1;//p0,p1,p2成顺时针方向
	if(dot(a,b)<-eps) return 2;//p2 p0 p1一次排列在同一直线上
	if(a.norm()<b.norm()) return -2;// p0 p1 p2一次排列在同一直线上
	return 0;//p2在线段p0p1上

}
bool intersect(Point p1,Point p2,Point p3,Point p4)//判断是否相交 通过ccw来判断
{
	return (ccw(p1,p2,p3)*ccw(p1,p2,p4)<=0&&ccw(p3,p4,p1)*ccw(p3,p4,p2)<=0);
}



/*
点a与点b之间的距离等于向量a-b或b-a的绝对值。
*/
double getdis(Point a,Point b)//求俩点间的距离
{
	return (a-b).ABS();
}

/*
设直线p1 p2上的向量为a=p2-p1,p与p1构成的向量b=p-p1
则点p与直线p1p2的距离d就等于a,b构成的平行四边形的高
用a与b外积的大小(平行四边形的面积)除以a的大小|a|即可求出高d
d=|a*b|/|a|=|(p2-p1)*(p-p1)|/|p2-p1|;
*/
//注意：这里Segmet s是不规范的应该是 Line s 才对
double getdis_Li(Segment s,Point p)//点与直线的距离
{
	return abs(cross(s.p2-s.p1,p-s.p1)/(s.p2-s.p1).ABS());
}

double getdis_sp(Segment s,Point p)//点与线段的距离
{
	if(dot(s.p2-s.p1,p-s.p1)<0.0) return (p-s.p1).ABS();
	if(dot(s.p1-s.p2,p-s.p2)<0.0) return (p-s.p2).ABS();
	return getdis_Li(s,p);
}

double getdis_ss(Segment s1,Segment s2)//线段与线段之间的距离
{
	if(intersect(s1.p1,s1.p2,s2.p1,s2.p2)) return 0.0;
	return min(min(getdis_sp(s1,s2.p1),getdis_sp(s1,s2.p2)),min(getdis_sp(s2,s1.p1),getdis_sp(s2,s1.p2)));
}


int main()
{
	int T;scanf("%d",&T);
	while(T--){
		double x0,y0,x1,y1,x2,y2,x3,y3;
		scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&x0,&y0,&x1,&y1,&x2,&y2,&x3,&y3);
		Point p0(x0,y0),p1(x1,y1),p2(x2,y2),p3(x3,y3);
		Segment s1(p0,p1),s2(p2,p3);
		printf("%.10f\n",getdis_ss(s1,s2));
	}

	return 0;

}