## DMOPC '22 Contest 4 P3 - K-Knight

View as PDF

Points: 15
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

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.

#### 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