在二维平面上，两点 $(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$ 内部或边界上的点 $(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|)} \le 10^{-6}$ 时，该解将被接受。

样例

输入 1

1
0 0 2 1
4 5 5 2

输出 1

4.2639320225