题目内容

在一个无限大的二维棋盘上，一枚棋子从起点 $(x_1, y_1)$ 出发，想要到达终点 $(x_2, y_2)$。棋子有两种移动方式：

1. 对角线滑行：沿斜率为 $1$ 或 $-1$ 的对角线方向移动任意整数距离。即从 $(x, y)$ 可以一步到达 $(x+k, y+k)$ 或 $(x+k, y-k)$，其中 $k$ 为任意整数。
2. L 形跳跃：类似象棋中马的走法，每次移动的横向和纵向位移的绝对值分别为 1 和 2（顺序任意）。即一步可以到达 $(x+a, y+b)$，其中 $|a|+|b|=3$ 且 $1 \le |a|, |b| \le 2$。

现在有 $t$ 组询问，每组询问给定起点和终点坐标，请计算棋子从起点到终点最少需要多少步。

约束条件：询问组数 $t$ 不超过 100，所有坐标的绝对值不超过 $10^9$。

输入描述

第一行包含一个整数 $t$，表示询问组数。 接下来 $t$ 行，每行包含四个整数 $x_1, y_1, x_2, y_2$，分别表示起点和终点的坐标。

输出描述

对于每组询问，输出一行一个整数，表示从起点到终点的最少操作次数。

样例1

输入

3
0 0 2 1
0 0 2 4
0 0 3 1

输出

1
2
2

说明

第一组：从 $(0,0)$ 到 $(2,1)$。位移为 $(2,1)$，恰好是一个 L 形跳跃（$|2|+|1|=3$），只需 1 步。

第二组：从 $(0,0)$ 到 $(2,4)$。可以先用 L 形跳跃 $(1,2)$ 到达 $(1,2)$，再用 L 形跳跃 $(1,2)$ 到达 $(2,4)$，共 2 步。

第三组：从 $(0,0)$ 到 $(3,1)$。可以先用 L 形跳跃 $(1,2)$ 到达 $(1,2)$，再用 L 形跳跃 $(2,-1)$ 到达 $(3,1)$，共 2 步。

样例2

输入

2
5 5 5 5
0 0 -3 3

输出

0
1

说明

第一组：起点和终点相同，不需要移动，答案为 0。

第二组：从 $(0,0)$ 到 $(-3,3)$。位移为 $(-3,3)$，满足 $dx = -dy$，即沿斜率为 $-1$ 的对角线方向，只需 1 步对角线滑行即可到达。

样例3

输入

1
0 0 1 0

输出

2

说明

从 $(0,0)$ 到 $(1,0)$。位移为 $(1,0)$，既不在对角线上也不是 L 形跳跃，无法一步到达。

可以通过 2 步到达：先用 L 形跳跃 $(2,1)$ 到达 $(2,1)$，再从 $(2,1)$ 沿斜率为 $-1$ 的对角线方向滑行 $(-1,-1)$ 到达 $(1,0)$。即 L 形跳跃 + 对角线滑行，共 2 步。