Nahida is investigating a new chess piece she invented called the K-Knight! In one move, the K-Knight moves one square in one direction, and at least and at most
squares in a perpendicular direction. For instance, if the K-Knight steps one square to the right, it can then move between
and
squares either up or down.
Nahida has an infinite 2-D board, and she denotes the square on the -th row and the
-th column as square
. Out of curiosity, she places the K-Knight on square
and wonders: what's the least number of moves to get the K-Knight to square
?
To make sure you know what you're doing, Nahida will reset time and play the game with you times.
Constraints
Input Specification
The first line contains , the number of times Nahida will play a game with you.
Each of the next lines will contain three integers,
,
, and
.
Output Specification
For each game, output the minimum number of moves it will take to reach square . If it is impossible to reach
, output
-1
.
Sample Input
3
1 4 3
7 2 3
0 0 100
Sample Output
2
3
0
Comments