Description

Bookworm needs to move his tunnel boring machine.

Bookworm models the MC space as a 2D plane. His tunnel boring machine is currently at $(a,b)$, and he wants to move it to $(c,d)$.

In each step, Bookworm can move the machine one unit to the east, south, west, or north. However, the machine has a restriction: two consecutive steps cannot be taken in the same direction.

Given $(a,b)$ and $(c,d)$, compute the minimum number of steps Bookworm needs to move the machine to the destination.

Output the minimum number of steps. It can be proven that he can always reach the destination.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, representing the number of test cases.

The next $T$ lines each contain four integers $a,b,c,d$, representing one test case, where $(a,b)$ is the starting point and $(c,d)$ is the ending point.

Output Format

Output $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.

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

1
5
4

Hint

Explanation for Sample 1

• For the first test case, an optimal strategy is $(-2,0)\rarr(-2,1)$.
• For the second test case, an optimal strategy is $(0,1)\rarr(1,1)\rarr(1,2)\rarr(2,2)\rarr(2,3)\rarr(3,3)$.
• For the third test case, one optimal strategy is $(-1,1)\rarr (0,1)\rarr(0,0)\rarr(1,0)\rarr(1,1)$.

Constraints

This problem uses bundled testdata.

• Subtask 1 (29 pts): $0\le a,b,c,d\le 3$.
• Subtask 2 (29 pts): $a=c$.
• Subtask 3 (42 pts): no special restrictions.

For all testdata, $1\le T\le 10^5$, $|a|,|b|,|c|,|d|\le 10^{18}$.

Translated by ChatGPT 5