Drone Delivery Navigation

You are given a grid with N rows and M columns representing a city. Some cells of the grid contain obstacles through which a delivery drone cannot pass. The drone can move only in the four cardinal directions (up, down, left, and right). Given the starting position and the destination position, your task is to determine the minimum number of moves required for the drone to reach the destination while avoiding obstacles.

If the destination is unreachable, output -1. Note that if the drone starts at the destination, the minimum number of moves is 0.

The movement can be mathematically represented using breadth-first search (BFS) on a grid. If we denote a move from cell \((x, y)\) as one of the following transitions:

[ (x-1, y), \quad (x+1, y), \quad (x, y-1), \quad (x, y+1), ]

then the minimum number of moves corresponds to the shortest path length from the start to the destination avoiding obstacles.

inputFormat

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

T
N M O
r1 c1
r2 c2
... (O lines of obstacles, if O > 0)
sx sy
dx dy
... (The above block repeats T times for each test case)

Where:

• T is the number of test cases.
• N and M are the number of rows and columns respectively.
• O is the number of obstacles.
• Each of the next O lines contains two integers r and c denoting the coordinates of an obstacle.
• sx sy are the starting coordinates of the drone.
• dx dy are the destination coordinates.

outputFormat

For each test case, output a single integer representing the minimum number of moves required to reach the destination. If the destination is unreachable, output -1. The answers for multiple test cases should be printed on separate lines to stdout.

## sample

4
5 5 3
1 2
3 2
2 3
0 0
4 4
3 3 0
1 1
2 2
3 3 2
1 0
0 1
0 0
2 2
3 3 0
0 0
0 0

8
2
-1
0

</p>