题目描述

题面简述

Sam 住在 Awesomeburg，其市中心为三角形。 此外，三角形满足：

• 它的顶点具有整数坐标。
• 它的顶点具有非负坐标。
• 它的顶点不会共线。

如果他可以从 X 轴的至少一个点沿着某条直线行走而不穿过三角形的内部，他就称市中心边界上的一个点（即三角形的边界）是安全的。

在图片中，市中心用灰色标记。

第一条路径无效，因为它不沿着直线走。

第二条路径无效，因为它与市中心的内部相交。

第三条和第四条路径是正确的。

求市区边界不安全部分的总长度。 可以证明，这些部分是段，它们的数量是有限的。

输入格式

每个测试包含多个测试用例。 第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。每一组测试用例的描述如下：

每个测试用例包含三行，每行包含两个整数 $x, y$（$0 \le x_i, y_i \le 10^9$），表示市中心边界顶点的坐标。

输出格式

为每个测试用例输出问题的答案。

如果绝对或相对误差不超过 $10^{-9}$，则您的答案将被视为正确。

样例

5
8 10
10 4
6 2
4 6
0 1
4 2
14 1
11 2
13 2
0 0
4 0
2 4
0 1
1 1
0 0

0.0000000
0
2.0000
0.00
1