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