题目描述

书虫需要移动他的盾构机。

书虫将 MC 空间抽象为二维平面。他的盾构机现在在 $(a,b)$，而书虫想把盾构机移动到 $(c,d)$。

书虫每一步可以将盾构机向东南西北任何方向行动。但是这盾构机有一个限制：相邻两步不能向同一个方向走！

给定 $(a,b)$ 和 $(c,d)$，请计算书虫最少需要几步将盾构机移动到终点。

求书虫的最少步数。可以证明，他永远可以到达终点。

输入格式

本题有多组数据。

第一行一个正整数 $T$，表示表示数据的组数。

接下来 $T$ 行，每行四个整数 $a,b,c,d$，代表一组数据，其中 $(a,b)$ 为起点，$(c,d)$ 为终点。

输出格式

输出 $T$ 行，第 $i$ 行代表第 $i$ 组数据的答案。

3
-2 0 -2 1
0 1 3 3
-1 1 1 1

1
5
4

提示

样例 1 解释

• 对于第一组，最优策略为 $(-2,0)\rarr(-2,1)$。
• 对于第二组，最优策略为 $(0,1)\rarr(1,1)\rarr(1,2)\rarr(2,2)\rarr(2,3)\rarr(3,3)$。
• 对于第三组，最优策略之一为 $(-1,1)\rarr (0,1)\rarr(0,0)\rarr(1,0)\rarr(1,1)$。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（29 pts）：$0\le a,b,c,d\le 3$。
• Subtask 2（29 pts）：$a=c$。
• Subtask 3（42 pts）：无特殊限制。

对于所有数据，$1\le T\le 10^5$，$|a|,|b|,|c|,|d|\le10^{18}$。