In the game of Chess, each type of piece moves across the board in a different way.
Unlike the other pieces which move in straight lines along the rows, columns, or diagonals, a knight's move involves moving 2 spaces along one axis, then 1 space along the other axis.
From his starting square, there are 8 possible squares the knight could end up on.
A knight located at the red circle could make any move indicated by a blue arrow, landing at any of the red crosses.
Imagine the knight is on an infinite chessboard, initially standing upon the square with coordinates (0, 0).
If the knight wanted to travel to the sqaure (0, 1), there are multiple possible paths he could take.
One possible path is (0, 0) -> (-1, 2) -> (1, 3) -> (0, 1).
This path brings him from his initial square to his destination in 3 moves.
There are other paths he could take to reach the (0, 1) square, but no path could bring him there in less than 3 moves.
Problem Statement
Given the coordinates of a square upon the infinite chessboard, determine the shortest number of turns required for the night to reach that sqaure starting from (0, 0).
Input Data
The first line will be Q, the quantity of testcases.
Q pairs of space-separated integer coordinates will follow as x y.
Answer
Should consist of Q space-separated values each, corresponding to the minimum turns required for a knight to move from (0, 0) to (x, y).
Example
input data:
5
-1 2
0 1
12345 -67890
answer:
1 3 33945