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 moves to repeat its position if allowed to move vertically. The snake takes 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 of possible positions for the snake and also for the reward, what is the minimum number of moves required for a snake at cell to reach a reward at cell .
The first line contains a single integer — the number of test cases.
Each of the following T lines consist of integers , .
Print the answer of each test case in a new line.
Input | Output |
---|---|
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 . In one upward move, it goes to . Next, it goes to with one leftward move. Sample 2: It starts at . With one rightward move, it goes to . After that, with consecutive upward moves, it reaches . |