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 PYTHON3):

Solution:
#!/usr/bin/python3

import array
from fractions import Fraction
import math
import os
import sys


def main():
    Q = read_int()
    for _ in range(Q):
        x0, y0, x1, y1, x2, y2, x3, y3 = read_ints()
        print(solve(Vec(x0, y0), Vec(x1, y1), Vec(x2, y2), Vec(x3, y3)))


def pairwise_min2(a, b, c):
    return min(b.abs2(), c.abs2(),
               (b - a).abs2(), (c - a).abs2())


def calc3(a, b, c):
    c_ab = a.cross(b)
    c_ac = a.cross(c)
    if c_ab == 0 and c_ac == 0:  # on line
        s = Fraction(a.dot(b), a.abs2())
        t = Fraction(a.dot(c), a.abs2())
        if s < 0 and t < 0:
            return (max(s, t) * a).abs2()
        if s > 1 and t > 1:
            return ((min(s, t) - 1) * a).abs2()
        return 0

    cb = c - b
    c_acb = a.cross(cb)
    if c_acb != 0:  # not parallel
        u = Fraction(b.cross(cb), c_acb)
        v = Fraction(b.cross(a), c_acb)
        if 0 <= u <= 1 and 0 <= v <= 1:
            return 0  # crossed

    d_cba = cb.dot(a)
    if d_cba == 0:  # orthogonal
        s = Fraction(b.dot(a), a.abs2())
        if 0 <= s <= 1:
            sa = s * a
            return min((b - sa).abs2(), (c - sa).abs2())
        return pairwise_min2(a, b, c)

    d_ba = b.dot(a)
    d_ca = c.dot(a)
    a2 = a.abs2()
    s = Fraction(d_ba, a2)
    t = Fraction(d_ca, a2)
    p = Fraction(-d_ba, d_cba)
    q = Fraction(a2 - d_ba, d_cba)

    dists = [pairwise_min2(a, b, c)]
    if 0 <= s <= 1:
        dists.append((b - s * a).abs2())
    if 0 <= t <= 1:
        dists.append((c - t * a).abs2())
    if 0 <= p <= 1:
        dists.append((b + p * cb).abs2())
    if 0 <= q <= 1:
        dists.append((b + q * cb - a).abs2())

    return min(dists)


def solve(u, v, w, x):
    return math.sqrt(min(calc3(v - u, w - u, x - u),
                         calc3(x - w, u - w, v - w)))


###############################################################################
# AUXILIARY FUNCTIONS

class Vec(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y
        super().__init__()

    def __add__(self, other):
        return Vec(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Vec(self.x - other.x, self.y - other.y)

    def __mul__(self, scalar):
        return Vec(self.x * scalar, self.y * scalar)

    def __rmul__(self, scalar):
        return Vec(self.x * scalar, self.y * scalar)

    def __truediv__(self, scalar):
        return Vec(self.x / scalar, self.y / scalar)

    def __iadd__(self, other):
        self.x += other.x
        self.y += other.y
        return self

    def __isub__(self, other):
        self.x -= other.x
        self.y -= other.y
        return self

    def __imul__(self, scalar):
        self.x *= scalar
        self.y *= scalar
        return self

    def __idiv__(self, scalar):
        self.x /= scalar
        self.y /= scalar
        return self

    def __neg__(self):
        return Vec(-self.x, -self.y)

    def dot(self, other):
        return self.x * other.x + self.y * other.y

    def cross(self, other):
        return self.x * other.y - self.y * other.x

    def abs2(self):
        return self.x * self.x + self.y * self.y

    def __abs__(self):
        return math.sqrt(float(self.abs2()))

    def __str__(self):
        return '({}, {})'.format(self.x, self.y)


DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()