DMOPC '22 Contest 4 P3 - K-Knight

View as PDF

Submit solution


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 1 and at most K squares in a perpendicular direction. For instance, if the K-Knight steps one square to the right, it can then move between 1 and K squares either up or down.

Nahida has an infinite 2-D board, and she denotes the square on the i-th row and the j-th column as square (i, j). Out of curiosity, she places the K-Knight on square (0, 0) and wonders: what's the least number of moves to get the K-Knight to square (x, y)?

To make sure you know what you're doing, Nahida will reset time and play the game with you T times.

Constraints

1 \le T \le 5 \times 10^5

0 \le x, y \le 10^9

2 \le K \le 10^9

Input Specification

The first line contains T, the number of times Nahida will play a game with you.

Each of the next T lines will contain three integers, x, y, and K.

Output Specification

For each game, output the minimum number of moves it will take to reach square (x, y). If it is impossible to reach (x, y), output -1.

Sample Input

3
1 4 3
7 2 3
0 0 100

Sample Output

2
3
0

Comments

There are no comments at the moment.