题目描述
书虫需要移动他的盾构机。
书虫将 MC 空间抽象为二维平面。他的盾构机现在在 (a,b),而书虫想把盾构机移动到 (c,d)。
书虫每一步可以将盾构机向东南西北任何方向行动。但是这盾构机有一个限制:相邻两步不能向同一个方向走!
给定 (a,b) 和 (c,d),请计算书虫最少需要几步将盾构机移动到终点。
求书虫的最少步数。可以证明,他永远可以到达终点。
输入格式
本题有多组数据。
第一行一个正整数 T,表示表示数据的组数。
接下来 T 行,每行四个整数 a,b,c,d,代表一组数据,其中 (a,b) 为起点,(c,d) 为终点。
输出格式
输出 T 行,第 i 行代表第 i 组数据的答案。
提示
样例 1 解释
- 对于第一组,最优策略为 (−2,0)→(−2,1)。
- 对于第二组,最优策略为 (0,1)→(1,1)→(1,2)→(2,2)→(2,3)→(3,3)。
- 对于第三组,最优策略之一为 (−1,1)→(0,1)→(0,0)→(1,0)→(1,1)。
数据规模与约定
本题采用捆绑测试。
- Subtask 1(29 pts):0≤a,b,c,d≤3。
- Subtask 2(29 pts):a=c。
- Subtask 3(42 pts):无特殊限制。
对于所有数据,1≤T≤105,∣a∣,∣b∣,∣c∣,∣d∣≤1018。