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