城市的地下管网中检测到了严重的漏水！小青鱼获取了主要输水管道的布局，布局显示城市下方有 $n$ 条老化的主要输水管道。在二维示意图中，每条管道都被建模为平面上的一条无限长的直线。

为了快速堵住漏水点并恢复供水，城市部署了一套新的应急修复系统：一个可伸缩的机器人修复臂，它可以从地面插入并作为一条线段延伸到地下。

该修复臂配备了智能连接器，只要该线段与水管相交（即至少有一个公共点），它就可以自动对接并进行现场密封和修复。然而，修复臂的成本和机械复杂度与其长度成正比。此外，地质约束限制了修复臂在地下横向延伸的距离。

两个样例答案的示意图。

因此，小青鱼必须确定这样一条与所有 $n$ 条水管相交的线段的最小可能长度。作为城市智能基础设施部门的首席算法工程师，小青鱼被紧急授权解决这一关键的几何优化问题。

输入格式

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

对于每组测试数据，第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示管道的数量。

接下来的 $n$ 行，每行包含四个整数 $x_1, y_1, x_2$ 和 $y_2$ ($-10^3 \le x_1, y_1, x_2, y_2 \le 10^3$, $(x_1, y_1) \ne (x_2, y_2)$)，表示一条穿过点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的管道。

保证所有测试数据的 $n$ 之和不超过 $10^5$。

输出格式

对于每组测试数据，输出一行，包含一个实数，表示与所有 $n$ 条水管相交的线段的最小长度。

如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。具体来说，假设你的输出为 $a$，裁判的答案为 $b$，当且仅当 $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$ 时，你的输出才会被接受。

样例

样例输入 1

3
3
0 0 2 0
2 0 1 2
1 2 0 0
4
0 0 1 0
1 0 1 1
1 1 0 1
0 1 0 0
1
0 0 1 1

样例输出 1

1.788854381948
1.414213562373
0