题目描述

在二维平面上，两点 $(x_1,y_1)$ 和 $(x_2,y_2)$ 之间的曼哈顿距离是 $|x_1-x_2|+|y_1-y_2|$ 。如果一个点的两个坐标都是整数，那么我们称这个点为整数点。

给定二维平面上的两个圆 $C_1,C_2$ ，并保证 $C_1$ 中任意一点的 $x$ 坐标与 $C_2$ 中任意一点的 $x$ 坐标不同，且 $C_1$ 中任意一点的 $y$ 坐标与 $C_2$ 中任意一点的 $y$ 坐标不同。

每个圆都由两个整数点描述，连接两点的线段代表圆的直径。

现在需要在 $C_2$ 内或 $C_2$ 上选择一个点 $(x_0,y_0)$ ，使得从 $(x_0,y_0)$ 到 $C_1$ 内的点的曼哈顿距离的期望值最小(从 $C_1$ 内所有实数坐标点中均匀概率地选择一点)。

输入格式

第一行包含一个整数 $t (1\le t\le 10^5)$ 。表示测试用例的数量。

第一行包含 $4$ 个整数 $x_{1,1},y_{1,1},x_{1,2},y_{1,2}$ ，代表连接 $(x_{1,1},y_{1,1})$ 和 $(x_{1,2},y_{1,2})$ 的线段，是圆 $C_1$ 的直径。

第二行包含 $4$ 个整数 $x_{2,1},y_{2,1},x_{2,2},y_{2,2}$ ，表示连接 $(x_{2,1},y_{2,1})$ 和 $(x_{2,2},y_{2,2})$ 的线段，是圆 $C_2$ 的直径。

所有输入的坐标都是范围为 $[-10^5, 10^5]$ 的整数。

输出格式

对于每个测试案例，输出一个实数表示最小预期曼哈顿距离。

如果答案的相对误差不超过 $10^{-6}$ ，则视为正确答案。也就是说，如果你的答案是 $a$ ，而答案是 $b$ ，那么如果 $\frac{|a-b|}{\max (1,|b|)} \leq 10^{-6}$ ，答案也视为正确。

样例

1
0 0 2 1
4 5 5 2

4.2639320225