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>
#include<stdio.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) begin(a),end(a)
#define MS(m,v) memset(m,v,sizeof(m))
#define D10  fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> P;
typedef long long ll;
const ll INF = 114514810;
const ll MOD = 1000000007;
const double EPS = 1e-8;
const double PI = acos(-1.0);
struct edge
{
	int to, cost;
	bool operator < (const edge& e) const { return cost < e.cost; }
	bool operator >(const edge& e) const { return cost > e.cost; }
};
int dx[] = { -1, 0, 0, 1 }; int dy[] = { 0, -1, 1, 0 };
bool valid(int x, int y, int h, int w) { return (x >= 0 && y >= 0 && x < h&&y < w); }
///*************************************************************************************///
///*************************************************************************************///
///*************************************************************************************///

bool eq(double a, double b) { return fabs(a - b) < EPS; }

struct point
{
	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 s) { return point(x * s, y * s); }
	point operator / (double s) { return point(x / s, y / s); }

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

	bool operator < (const point &p) const
	{
		return x != p.x ? x < p.x : y < p.y;
	}

	bool operator == (const point &p) const
	{
		return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
	}

};

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

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

struct line
{
	point a, b;
	line(double x1 = 0, double y1 = 0, double x2 = 0, double y2 = 0) :a(point(x1, y1)), b(point(x2, y2)) {};
	line(point p, point q) :a(p), b(q) {};
	point univec() { return (b - a) / (b - a).norm(); }
};

int ccw(point a, point b, point c)
{
	b = b - a; c = c - a;
	if (cross(b, c) > EPS) return 1;
	if (cross(b, c) < -EPS) return -1;
	if (dot(b, c) < 0) return 2;
	if (b.norm() < c.norm()) return -2;
	return 0;
}

bool isis_sp(line s, point p)
{
	return ((s.a - p).abs() + (s.b - p).abs() - (s.b - s.a).abs()) < EPS;
}

bool isis_ss(line s, line t)
{
	return (ccw(s.a, s.b, t.a)*ccw(s.a, s.b, t.b) <= 0 &&
		ccw(t.a, t.b, s.a)*ccw(t.a, t.b, s.b) <= 0);
}

point cross_point_ss(line s1, line s2)
{
	point base = s2.b - s2.a;
	double d1 = abs(cross(base, s1.a - s2.a));
	double d2 = abs(cross(base, s1.b - s2.a));
	double t = d1 / (d1 + d2);
	return s1.a + (s1.b - s1.a)*t;
}

point projection(line l, point p)
{
	point base = l.b - l.a;
	double r = dot(p - l.a, base) / base.norm();
	return l.a + base*r;
}

double dist_sp(line s, point p)
{
	point r = projection(s, p);
	if (isis_sp(s, r)) return (r - p).abs();
	return min((s.a - p).abs(), (s.b - p).abs());
}

double dist_ss(line s1, line s2)
{
	if (isis_ss(s1, s2)) return 0;
	return min({ dist_sp(s1, s2.a), dist_sp(s1, s2.b),
		dist_sp(s2, s1.a), dist_sp(s2, s1.b) });
}

int main()
{
	int q; cin >> q;
	while (q--)
	{
		double x[4], y[4];
		REP(i, 4) cin >> x[i] >> y[i];
		line s(x[0], y[0], x[1], y[1]);
		line t(x[2], y[2], x[3], y[3]);
		cout << D10 << dist_ss(s, t) << endl;
	}
	return 0;
}