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 <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using flt = double;
const flt eps = 1e-12, inf = 1e18, PI = acos(-1.0);
template<typename T>
inline T sqr(T x) {return x * x;}
inline flt cmp(flt a, flt b, flt e = eps) {
  return fabs(a - b) >= e + fabs(a) * e ? a - b : 0;
}
inline int sgn(flt x, flt e = eps) {return x < -e ? -1 : (x > e);}
inline flt fix(flt x, flt e = eps) {return cmp(x, 0, e);}

struct point {
  flt x, y;
  point(flt x = 0, flt y = 0): x(x), y(y) {}
  bool operator < (const point &rhs) const {
    return cmp(x, rhs.x) < 0 || (cmp(x, rhs.x) == 0 && cmp(y, rhs.y) < 0);
  }
  bool operator == (const point &rhs) const {
    return cmp(x, rhs.x) == 0 && cmp(y, rhs.y) == 0;
  }
  point operator + (const point &rhs) const {
    return point(x + rhs.x, y + rhs.y);
  }
  point operator - (const point &rhs) const {
    return point(x - rhs.x, y - rhs.y);
  }
  point operator * (const flt k) const {
    return point(x * k, y * k);
  }
  point operator / (const flt k) const {
    return point(x / k, y / k);
  }
  point operator ~ () const {// counter clockwise rotate 90 degree
    return point(-y, x);
  }
  flt dot(const point &rhs) const {
    return x * rhs.x + y * rhs.y;
  }
  flt det(const point &rhs) const {
    return x * rhs.y - y * rhs.x;
  }
  flt norm2() const {
    return x * x + y * y;
  }
  flt norm() const {
    return hypot(x, y);
  }
  point rot(flt a) const {// counter clockwise rotate A rad
    return point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
  }
  point rot(flt cosa, flt sina) const {// counter clockwise rotate using cos/sin
    return point(x * cosa - y * sina, x * sina + y * cosa);
  }
  point trunc(flt a = 1.0) const {
    return (*this) * (a / this->norm());
  }
};

// check if point O is on segment AB
bool on_segment(const point &A, const point &B, const point &O) {
  return sgn((A - O).det(B - O)) == 0 && sgn((A - O).dot(B - O)) <= 0;
}

// check if AB is parallel to CD
bool is_parallel(const point &A, const point &B, const point &C, const point &D) {
  return sgn((B - A).det(D - C)) == 0;
}

// check intersection of segments AB and CD
bool segment_intersect(const point &A, const point &B, const point &C, const point &D, point &res) {
  if (on_segment(A, B, C)) {res = C; return true;}
  if (on_segment(A, B, D)) {res = D; return true;}
  if (on_segment(C, D, A)) {res = A; return true;}
  if (on_segment(C, D, B)) {res = B; return true;}
  point AB(B - A), CD(D - C);
  if (sgn(AB.det(CD)) == 0) return false; // parallel
  int d1 = sgn(AB.det(C - A)) * sgn(AB.det(D - A));
  int d2 = sgn(CD.det(A - C)) * sgn(CD.det(B - C));
  res = A + AB * (CD.det(C - A) / CD.det(AB));
  return d1 < 0 && d2 < 0;
}

// find the minimum distance from O to segment AB
flt dis_to_segment(const point &A, const point &B, const point &O) {
  if (sgn((O - A).dot(B - A)) < 0) return (O - A).norm();
  if (sgn((O - B).dot(A - B)) < 0) return (O - B).norm();
  return fabs((O - A).det(B - A) / (A - B).norm());
}

int main() {
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; ++i) {
    point A, B, C, D, O;
    scanf("%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y);
    scanf("%lf%lf%lf%lf", &C.x, &C.y, &D.x, &D.y);
    if (segment_intersect(A, B, C, D, O)) printf("%.10f\n", 0.0);
    else {
      printf("%.10f\n", std::min(std::min(dis_to_segment(A, B, C), dis_to_segment(A, B, D)), std::min(dis_to_segment(C, D, A), dis_to_segment(C, D, B))));
    }
  }
  return 0;
}