DreamGrid 正在无限大的二维平面上玩象棋。

DreamGrid 有两枚黑子：马和炮。只有一枚红子——帅，位于原点 $(0, 0)$。DreamGrid 想要以最少的步数吃掉红帅。为了降低难度，红帅在过程中不会移动。

炮和马的移动规则与标准象棋规则相同，包括“蹩马腿”规则。如果你不了解这些规则，可以参考下文的解释。

当你想要移动位于 $(x, y)$ 的马时，你需要先选择两个相互垂直的方向 $(dx_1, dy_1)$ 和 $(dx_2, dy_2)$，其中 $(dx_1, dy_1), (dx_2, dy_2) \in \{(1, 0), (-1, 0), (0, 1), (0, -1)\}$，并将马移动到 $(x + 2dx_1 + dx_2, y + 2dy_1 + dy_2)$。在大多数情况下，马可以移动到八个位置：$(x+2, y+1), (x+2, y-1), (x-2, y+1), (x-2, y-1), (x+1, y+2), (x+1, y-2), (x-1, y+2), (x-1, y-2)$。如果移动的目标位置上有对方棋子，马可以将其吃掉。

“蹩马腿”规则限制了马的移动。如果 $(x + dx_1, y + dy_1)$ 处有其他棋子（无论颜色），马就不能移动到 $(x + 2dx_1 + dx_2, y + 2dy_1 + dy_2)$。

在单步移动中，炮可以移动或攻击。它可以在水平或垂直方向上移动任意距离（每次选择其中一个方向），但在移动时不能跳过其他棋子。炮只能通过“炮架”攻击其他棋子。形式化地说，在炮的某个方向（上、下、左、右）上，如果有两枚或更多的棋子，且距离炮第二近的棋子是对方棋子，则炮可以吃掉该棋子并移动到该位置。

炮的攻击

马的移动

你能帮助 DreamGrid 以最少的步数吃掉红帅吗？

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 500\,000$)，表示测试数据组数。对于每组测试数据：

唯一一行包含四个整数 $x_h, y_h, x_c, y_c$ ($-10^9 \le x_h, y_h, x_c, y_c \le 10^9$)。马的初始位置为 $(x_h, y_h)$，炮的初始位置为 $(x_c, y_c)$。

保证马、炮和帅的初始位置互不相同。

输出格式

对于每组测试数据，输出一行，表示吃掉红帅所需的最少步数。

样例

样例输入 1

5
-2 1 5 5
5 0 6 0
2 1 1 1
100 2 -1 0
4 2 1 1

样例输出 1

1
1
2
5
3