Robot Movement: Minimum Steps to Corner

A robot is placed in the top-left corner of an n × m grid. The robot can move one step at a time in any of the four cardinal directions (up, down, left, right). Certain cells in the grid contain obstacles which the robot cannot pass through. Given the number of obstacles k and their positions (with positions provided in 1-indexed format), determine the minimum number of steps required for the robot to reach the bottom-right corner (n, m) starting from the top-left corner (1, 1). If reaching the bottom-right corner is impossible, output -1.

The problem can be modeled using a breadth-first search (BFS) on a grid. The movement cost between adjacent cells is 1, so the minimum number of moves is equal to the shortest path length. In mathematical terms, if we denote the number of steps by S, then the process finds the minimum S satisfying:

[ \text{start} + S \equiv (n, m) \quad \text{(via valid moves)} ]

Note: Obstacle positions are given in a 1-indexed format, but you may use 0-indexing internally to process the grid.

inputFormat

The input begins with an integer t representing the number of test cases.

Each test case starts with a line containing three integers n, m, and k (the number of rows, columns, and obstacles respectively). This is followed by k lines, each containing two integers x and y representing the position of an obstacle (1-indexed).

outputFormat

For each test case, output a single integer on a new line: the minimum number of steps from the top-left corner to the bottom-right corner. If it is impossible to reach the destination, output -1.

## sample

2
3 3 1
2 2
4 4 2
2 2
3 3

4
6

</p>