一家无人驾驶汽车公司在二维笛卡尔平面上拥有一个矩形实验场。其四条边均平行于坐标轴。该场地的左下角坐标为 $(x_l, y_l)$，右上角坐标为 $(x_r, y_r)$。

矩形内部严格包含两条线段 $A$ 和 $B$。$A$ 和 $B$ 没有公共点。平面上还有一辆可以看作点的汽车。它将从矩形边界上的点 $S$ 出发，移动到矩形内部的某个位置，最后停在矩形边界上的另一个点 $T$。实验要求汽车在移动过程中的任何时刻（包括汽车位于 $S$ 和 $T$ 时），汽车到线段 $A$ 的距离必须等于汽车到线段 $B$ 的距离。此外，$S$ 和 $T$ 必须是两个不同的点。点 $P$ 到线段 $Q$ 的距离定义为 $P$ 到 $Q$ 上任意一点的最小欧几里得距离。

上图对应样例测试

请编写一个程序，帮助公司找到一条合法的汽车移动路径，使得路径长度最小，或者确定不存在合法的路径。

输入格式

输入包含多组测试数据。输入的第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试数据的组数。

对于每组数据，第一行包含四个整数 $x_l, y_l, x_r, y_r$ ($-1000 \le x_l < x_r \le 1000$, $-1000 \le y_l < y_r \le 1000$)，表示矩形左下角和右上角的坐标。接下来的两行，每行包含四个整数 $x_1, y_1, x_2, y_2$，表示一条连接 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的线段，其中 $x_1, x_2 \in [x_l + 1, x_r - 1]$ 且 $y_1, y_2 \in [y_l + 1, y_r - 1]$。

对于每组数据，保证每条线段的两个端点不重合，且这两条线段没有公共点。

输出格式

对于每组数据，如果存在合法的路径，输出一行，包含一个实数，表示路径的最小长度。否则，输出数字 $0$。如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-9}$，则被视为正确。

形式上，如果你的答案是 $a$，标准答案是 $b$，则当且仅当 $\frac{|a-b|}{\max\{1,|b|\}} \le 10^{-9}$ 时，你的答案被视为正确。

样例

输入 1

1
0 0 7 6
2 4 4 4
3 2 5 2

输出 1

7.552593593868681136