Hide

Problem E
Malfunctioning Robot

Arthur is participating in the Vietnamese Robotic Olympiad $2\, 020$. In the first round, candidates must build a path-finding robot. More precisely, the organizers have prepared an infinite, obstacle-free grid. One candidate’s robot is placed at a starting position $(x_1, y_1)$ and must find a path to a target position $(x_2, y_2)$.

Arthur’s robot is quite simple: it can only move in four directions: up, down, left and right, i.e. from $(x, y)$, it can moves to $(x, y+1)$, $(x, y-1)$, $(x-1, y)$ and $(x+1, y)$.

The first round is starting soon. However, Arthur just realized that some of the robot’s components are broken, and thus the robot cannot move in the same direction in two consecutive moves (i.e. it always changes direction after each move). For example, if the robot needs to go from $(1, 1)$ to $(3, 3)$, the robot can use the path shown on the right, but not the path shown on the left.

\includegraphics[width=.9\textwidth ]{M.png}

Please help Arthur find the minimum number of moves for his robot to get from some starting position to some ending one.

Input

The input starts with $T$ - the number of test cases ($1 \leq T \leq 1\, 000$), then $T$ test cases follow. Each test case is presented in a single line with $4$ integers $x_1$, $y_1$, $x_2$ and $y_2$ which denote the starting and target position of the robot.

The absolute value of all integers in the input do not exceed $10^9$.

Output

For each test case, print the minimum number of moves for Arthur’s robot to get from $(x_1,y_1)$ to $(x_2,y_2)$

Sample Input 1 Sample Output 1
2
1 1 3 3
0 1 1 1
4
1

Please log in to submit a solution to this problem

Log in