Pang 教授买了一个人形清洁机器人来打扫他的院子。这个机器人不太智能，它每次只能选择向前移动或者改变方向，所有动作都由 Pang 教授的控制器控制。

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

现在 Pang 教授很懒，他想最小化机器人改变方向的次数。你能帮帮他吗？

输入格式

第一行包含一个整数 $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]$ 范围内。

输出格式

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

样例

输入 1

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

输出 1

0
0
1

说明

下图展示了第一个样例和第三个样例。