Knight's Shortest Path with Obstacles

You are given an N×N chessboard where a knight is placed at the top-left corner ((0, 0)), and the goal is to reach the bottom-right corner ((N-1, N-1)).

The knight moves in an L-shaped pattern. In particular, its possible moves are given by the set of translations \[ \{(\pm2,\pm1),\ (\pm1,\pm2)\} \] (in \(\LaTeX\) format). Some cells on the board are blocked by obstacles and cannot be visited.

Your task is to determine the minimum number of moves required to reach the target cell. If the destination cannot be reached, output -1.

inputFormat

The input is given from stdin and has the following format:

T
N M
K
x1 y1
x2 y2
... (K lines of obstacles)
... (repeated for each test case)

Here, T is the number of test cases. For each test case, N is the board dimension (so the board is N×N), and M is an auxiliary parameter. The next line contains an integer K representing the number of obstacles. The following K lines each contain two integers x and y, the coordinates of an obstacle. The knight always starts at (0, 0) and needs to reach (N-1, N-1).

outputFormat

For each test case, print a single integer on a new line: the minimum number of moves required for the knight to reach the destination, or -1 if it is not possible.

## sample

4
8 2
2
2 3
4 5
8 3
3
1 2
3 4
5 6
8 0
0
5 24
23
0 1
0 2
0 3
0 4
1 0
1 1
1 2
1 3
1 4
2 0
2 1
2 2
2 3
2 4
3 0
3 1
3 2
3 3
3 4
4 0
4 1
4 2
4 3

6
6
6
-1

</p>