B. Two Towers
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You have two towers made of blocks, standing next to each other. Initially, the height of the first tower is $$$a$$$, and the height of the second tower is $$$b$$$.

In one action, you can:

  • take one block and place it on one of the towers, increasing its height by $$$1$$$;
  • or take two blocks and place one on each tower, increasing both heights by $$$1$$$. However, this can only be done if their heights are equal.

Your goal is to make the height of the first tower equal to $$$c$$$, and the height of the second tower equal to $$$d$$$. What is the minimum number of actions you need to perform?

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of one line containing $$$4$$$ integers $$$a, b, c, d$$$ ($$$1 \le a \le c \le 10^8$$$; $$$1 \le b \le d \le 10^8$$$).

Output

For each test case, output one integer — the minimum number of actions that you have to perform.

Example
Input
5
1 2 3 5
1 1 1 1
2 6 3 8
3 3 6 4
2 4 7 7
Output
4
0
3
3
5
Note

In the first example, you can first place a block on the first tower, making the heights of both towers equal to $$$2$$$. Then, you can place one block on each tower, raising their heights to $$$3$$$. After that, you can place two blocks on the second tower, increasing its height to $$$5$$$. Thus, in $$$4$$$ moves, you can make the height of the first tower equal to $$$3$$$ and the second tower equal to $$$5$$$.