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