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