Description

庞教授买了一个人形清洁机器人来清理他的院子。这个机器人并不十分复杂，它可以前进或改变方向，这一切都由庞教授的控制器控制。

庞教授的院子是一个二维平面。机器人需要从当前位置 $A$ 移动到目的地 $B$，以满足庞教授的一些“清洁”需求。然而，庞教授的院子里有两堵直墙 $CD$ 和 $EF$。由于机器人笨拙，如果它碰到任何一堵墙（即使是端点），它就会摔倒。

由于庞教授很懒，他希望尽量减少机器人改变方向的次数。你能帮他吗？

Input Format

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

对于每个测试用例，第一行包含两个整数 $x_A, y_A$，表示点 $A$ 的坐标。第二行包含两个整数 $x_B, y_B$，表示点 $B$ 的坐标。第三行包含四个整数 $x_C, y_C, x_D, y_D$，表示第一堵墙的端点 $C$ 和 $D$ 的坐标。第四行包含四个整数 $x_E, y_E, x_F, y_F$，表示第二堵墙的端点 $E$ 和 $F$ 的坐标。

保证机器人的当前位置 $A$ 和目的地 $B$ 都不在任何墙上。一堵墙可能退化为一个点。可以证明机器人总能从 $A$ 移动到 $B$ 而不碰到任何墙。所有值都在 $[-10^9, 10^9]$ 范围内。

Output Format

对于每个测试用例，输出一个数字 $d$，表示最少的转弯次数。

3
0 0
1 1
2 2 3 3
4 4 5 5
0 0
1 1
2 2 3 3
2 2 3 3
0 0
10 10
10 0 0 10
1 1 2 2

0
0
1

Hint

以下是第一个样例和第三个样例的示意图。

题面翻译由 ChatGPT-4o 提供。