Cheating Knight

The land of the Black King is an infinitely wide flat surface, split without gaps into black and white squares like an endless chessboard. Every square has an area of exactly one square metre, and the squares sit on a perfect grid.

Sir Jumpsalot is a knight who lives in that land. The law says a knight may move only by jumping from the centre of one square to the centre of another, and the distance between those two centres must be exactly $\sqrt{D}$ metres. In chess the value of $D$ is fixed at 5, but other values appear here as well. The $D$ written into the law can be expressed as a sum of two squares, because a knight could not move at all otherwise.

Sir Jumpsalot does not like to play by the rules. He still covers exactly $\sqrt{D}$ metres in one jump, but he ignores the part about landing on the centre of a square. He lands on a corner of a square, or on the border between two squares, or on any other point of the plane, whichever suits him. The two pictures below show routes to a destination two squares across and three squares up, with $D = 5$.

a) Route for any normal, law abiding knight.

b) Route for the cheating Sir Jumpsalot.

Sir Jumpsalot starts at the centre of the square with coordinates $(0, 0)$ and has to reach the centre of the square with coordinates $(X, Y)$. Nothing blocks his way. Find the minimum number of jumps he needs.

The first line contains the number of test cases $T$. ($1 \le T \le 1000$)

Each of the next $T$ lines contains three space separated integers $D$, $X$ and $Y$, where $D$ is the square of the distance covered by a single jump and $(X, Y)$ is the destination square. ($1 \le D \le 10^8$, $-10^4 \le X, Y \le 10^4$) The value $D$ can always be written as a sum of two squares.

For each test case, print the minimum number of jumps $J$ on a line of its own.