题目描述

大学生活开始了！大学生活的开始是军训。

Pog 是一种长着两只脚的猪。Pog 的两只脚始终保持 $1$ 的距离，他总是站在二维平面上的某两个整点上。在军训时，数百数 Pog学会了一项特别的本领：旋转。具体规则如下：

• 每次操作，Pog 可以选择任意一只脚作为轴心点，然后将另一只脚绕这只脚进行 90° 的旋转（可以选择顺时针或逆时针方向）。

现在 Pog 站在了平面上的两个点，分别是 $(sx_1, sy_1)$ 与 $(sx_2, sy_2)$；他的目标是控制自己的两只脚，移动到另一组点 $(tx_1, ty_1)$ 和 $(tx_2, ty_2)$ 上。你只需要最终让这两只脚分别占据目标点即可，不要求脚的左右顺序与起始时保持一致。当然，不论怎么旋转，两只脚之间的距离始终保持为 $1$。

请你帮 Pog 计算：最少需要旋转多少次，他才能完成从起点到终点的转换？如果无论怎么旋转都无法到达目标状态，请输出 -1。

输入格式

本题有多组数据。第一行一个数据 $T (1 \leq T \leq 10^5)$ 表示数据组数。

对于每组数据，包含一行八个整数，分别是 $sx_1, sy_1, sx_2, sy_2, tx_1, ty_1, tx_2, ty_2 (|s *_ |, |t *_ | \leq 10^9)$。

保证 $|sx_1 - sx_2| + |sy_1 - sy_2| = |tx_1 - tx_2| + |ty_1 - ty_2| = 1$。

输出格式

对于每组数据，如果 Pog 可以到达终点，输出一行一个整数，表示最少需要的旋转次数。否则，输出 $-1$。

7
0 0 0 1 0 0 0 1
0 0 1 0 0 0 0 1
0 0 0 1 1 1 0 1
0 0 0 1 1 1 1 0
0 0 0 1 0 0 -1 0
0 0 1 0 0 1 -1 1
0 0 -1 0 40 50 40 51

0
1
1
2
1
2
101

解释 #1