Limits 1s, 512 MB

After a long and hectic Eid day you are finally relaxing. But then your 5 year old cousin comes and wants to play games on your phone. Luckily you still have a nokia 1600. You open snake xenzia in the legendary phone, activate a cheat code to make the snake never grow, hand it over to the kid and watch as he plays.

If the snake moves out of screen from the top, it reappears from the bottom in the same column. If the snake moves out of screen from the left, it reappears from the right in the same row. Similar thing occurs for bottom and right. You notice that the snake takes 1616 moves to repeat its position if allowed to move vertically. The snake takes 2020 moves to repeat its position if allowed to move horizontally. A move can be defined as movement of the snake in one unit time, upward, downward, to the left or to the right. The goal of the snake is to eat a reward located somewhere on the screen.

Now you wonder, if the whole screen is regarded as a grid of size 16×2016\times20 of possible positions for the snake and also for the reward, what is the minimum number of moves required for a snake at cell (i1,j1)(i_1, j_1) to reach a reward at cell (i2,j2)(i_2, j_2).

Input

The first line contains a single integer T(1T30)T (1 \leq T \leq 30)— the number of test cases.

Each of the following T lines consist of 44 integers i1,j1,i2,j2i_1, j_1, i_2, j_2, (1i1,i216,1j1,j220)(1 \leq i_1, i_2 \leq 16, 1 \leq j_1, j_2 \leq 20 ).

Output

Print the answer of each test case in a new line.

Sample

InputOutput
5
1 1 16 20
4 20 16 1
9 9 9 9
1 15 16 15
10 10 15 15
2
5
0
1
10

Sample 1: Snake starts at (1,1)(1,1). In one upward move, it goes to (16,1)(16,1). Next, it goes to (16,20)(16,20) with one leftward move.

Sample 2: It starts at (4,20)(4,20). With one rightward move, it goes to (4,1)(4,1). After that, with 44 consecutive upward moves, it reaches (16,1)(16,1).


Submit

Login to submit.

Statistics

95% Solution Ratio
rkb_rdEarliest, Aug '22
naeem4265Fastest, 0.0s
naeem4265Lightest, 5.5 kB
pathanShortest, 149B
Toph uses cookies. By continuing you agree to our Cookie Policy.