Minimum Knight Moves on Chessboard with Obstacles

On an 8×8 chessboard, a knight is placed on a starting position and must reach a destination position. The knight moves in an L-shape: two squares in one direction and then one square perpendicular. However, some cells are blocked by obstacles which the knight cannot traverse.

Given the starting position \((sx, sy)\) and the destination \((dx, dy)\), along with a list of blocked cells, determine the minimum number of moves needed for the knight to reach the destination. If it is impossible to reach the destination, output \(-1\).

Constraints:

• \(0 \leq sx, sy < 8\) and \(0 \leq dx, dy < 8\)
• Obstacles are given as a list of coordinates \((ox, oy)\) with \(0 \leq ox, oy < 8\).

inputFormat

The input begins with an integer \(T\) representing the number of test cases.

Each test case has the following format:

sx sy dx dy
k
ox1 oy1
ox2 oy2
... 
oxk oyk

Here, \(sx\) and \(sy\) represent the starting coordinates, \(dx\) and \(dy)\) the destination coordinates, and \(k\) is the number of obstacles, followed by \(k\) lines each containing the coordinates of an obstacle.

outputFormat

For each test case, print a single integer representing the minimum number of moves required for the knight to reach the destination, or \(-1\) if it is impossible. Each result should be printed on a separate line.

## sample

1
0 0 7 7
0

6

</p>