Minimum Knight Moves

Given an n×n chessboard, a knight is placed at the starting position (1, 1). The knight moves in an L-shape as defined by the following moves: \( (2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1) \). For a given destination cell (x, y) on the board, determine the minimum number of moves required for the knight to reach that cell. If the destination is unreachable from the starting position, output \(-1\).

The input consists of several test cases. For each test case, the first line contains a single integer \(T\) representing the number of test cases. Each of the following \(T\) lines contains three space-separated integers \(n, x, y\), where \(n\) is the board size and \(x, y\) is the destination cell. The knight always starts at cell (1, 1).

It is assumed that \(1 \leq n \leq 50\) (for example) and that \(1 \leq x, y \leq n\). Compute the minimum moves needed for each test case. Each result should be output on a separate line.

inputFormat

The first line of input contains an integer \(T\), the number of test cases. Each of the following \(T\) lines contains three space-separated integers \(n, x, y\):

• n: the size of the chessboard (\(n \times n\)).
• x and y: the destination coordinates on the board.

outputFormat

For each test case, output a single integer on a new line representing the minimum number of moves required for the knight to reach the destination cell from position (1, 1). If the destination is unreachable, output \(-1\).

## sample

1
8 8 8

6

</p>