CF1642A.Hard Way

Sam lives in Awesomeburg, its downtown has a triangular shape. Also, the following is true about the triangle:

• its vertices have integer coordinates,
• the coordinates of vertices are non-negative, and
• its vertices are not on a single line.

He calls a point on the downtown's border (that is the border of the triangle) safe if he can reach this point from at least one point of the line $y = 0$ walking along some straight line, without crossing the interior of the triangle.

In the picture the downtown is marked with grey color. The first path is invalid because it does not go along a straight line. The second path is invalid because it intersects with the interior of the downtown. The third and fourth paths are correct.

Find the total length of the unsafe parts of the downtown border. It can be proven that these parts are segments and their number is finite.

山姆住在“极好堡”（Awesomeburg），该城市的市中心呈三角形。此外，该三角形满足以下条件：

• 其顶点坐标均为整数；
• 顶点坐标均非负；
• 三个顶点不共线。

他将市中心边界（即该三角形的边界）上的一点称为安全点，如果存在某条从直线 $y = 0$ 上某点出发的直线路径，能到达该点，且不穿过三角形内部。

图中灰色区域表示市中心。第一条路径无效，因为它不是直线；第二条路径无效，因为它与市中心内部相交；第三条和第四条路径是合法的。

请计算市中心边界上所有不安全部分的总长度。可以证明：这些不安全部分均由若干线段构成，且线段数量有限。

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Description of the test cases follows.

Each test case contains three lines, each of them contains two integers $x_i$, $y_i$ ($0 \le x_i, y_i \le 10^9$) — coordinates of the vertices of the downtown's border.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。随后是测试用例的描述。

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

For each test case print a single number — the answer to the problem.

Your answer will be considered correct if its absolute or relative error does not exceed $10^{-9}$. Formally let your answer be $a$, jury answer be $b$. Your answer will be considered correct if $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-9}$.

对于每个测试用例，输出一个数字——即该问题的答案。

若你的答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。形式化地，设你的答案为 $a$，评测组的答案为 $b$，当且仅当 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-9}$ 时，你的答案被视为正确。

In the picture, the downtowns of the first three test cases are illustrated. Triangles are enumerated according to the indices of test cases they belong to.

In the first two test cases, all points on the borders of the downtowns are safe, thus the answers are $0$.

In the following picture unsafe points for the third test case are marked with black color:

In the fourth test case, all points on the border of the downtown are safe.

图中展示了前三个测试用例的市中心区域。三角形按照其所属测试用例的编号进行编号。

在前两个测试用例中，市中心边界的全部点均为安全点，因此答案为 $0$。

在下图中，第三个测试用例中的不安全点以黑色标出：

在第四个测试用例中，市中心边界的全部点均为安全点。