H. Hututu
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Little A has obtained a Hututu.

The Hututu initially starts at the grid point $$$(x,y)$$$. In each turn, it can move to one of the following positions: $$$(x \pm 1,y \pm 1)$$$, $$$(x \pm 2,y \pm 2)$$$, $$$(x \pm 1,y\pm 2)$$$, or $$$(x \pm 2,y \pm 1)$$$. Hututu hopes to reach the grid point $$$(X,Y)$$$. The question is, what is the minimum number of turns he needs to take?

Input

The first line contains a positive integer $$$T$$$ $$$(1 \leq T \leq 10^6)$$$, indicating the number of test cases.

For each test case, there is a line with four integers $$$x,y,X,Y$$$ $$$(-10^9 \leq x,y,X,Y \leq 10^9)$$$, representing a query.

Output

For each test case, output a line with a single integer representing the answer.

Example
Input
3
1 2 1 2
1 1 3 4
1 1 98 98
Output
0
2
49