题目描述

给定一个无限大的二维平面网格图，初始时你在坐标 $(x,y)$。你可以按照如下规则进行移动：

• $(x \pm 1,y \pm 1)$
• $(x \pm 2,y \pm 2)$
• $(x \pm 1,y\pm 2)$
• $(x \pm 2,y\pm 1)$

现在给定你终点坐标 $(a,b)$，你需要输出从 $(x,y)$ 到 $(a,b)$ 的最少移动次数。

输入格式

第一行输入一个正整数 $t$，表示测试用例的数量。

接下来 $t$ 行，每行输入四个整数 $x,y,a,b$，表示起点坐标和终点坐标。

$(1\le t\le 10^5,-10^9\le x,y,a,b\le 10^9)$

输出格式

输出 $t$ 行，每行输出一个整数表示答案。

样例输入

3
1 2 1 2
1 1 3 4
1 1 98 98

样例输出

0
2
49