Minimum Platform Jumps

You are given a set of rectangular platforms in a 2D plane. Each platform is specified by its bottom-left (X1, Y1) and top-right (X2, Y2) integer coordinates. A player starts at a point (Sx, Sy) and aims to reach a target point (Tx, Ty). The player can only move by jumping from one platform to an adjacent platform. Two platforms are considered adjacent if they exactly touch each other along either a vertical or horizontal boundary. Note that overlap is also considered as adjacency if the shared boundary is exact.

Your task is to determine the minimum number of platform jumps required for the player to reach the target platform. If the start or target point is not located on any platform, or if the target cannot be reached, output -1. If the start and the target lie on the same platform, then 0 jumps are needed.

The adjacency condition between two platforms p₁ = (X1, Y1, X2, Y2) and p₂ = (X1', Y1', X2', Y2') is defined as follows (in LaTeX format):

\[ \text{Two platforms are adjacent if either } \left( X1 \leq X2' \; \text{and} \; X2 \geq X1' \; \text{and} \; \Big( Y1 = Y2' \; \text{or} \; Y2 = Y1' \Big) \right) \quad \text{or} \quad \left( Y1 \leq Y2' \; \text{and} \; Y2 \geq Y1' \; \text{and} \; \Big( X1 = X2' \; \text{or} \; X2 = X1' \Big) \right). \]

inputFormat

The input begins with an integer T, representing the number of test cases. For each test case, the first line contains four integers: Sx, Sy, Tx, Ty. The next line contains an integer P, the number of platforms. Then P lines follow, each containing four integers X1, Y1, X2, Y2, describing a platform.

All input values are space-separated.

outputFormat

For each test case, output a single integer on its own line, representing the minimum number of jumps required to reach the target platform. Output -1 if the target is unreachable.

2
0 0 10 10
3
0 0 2 2
2 2 5 5
5 5 10 10
0 0 3 3
3
0 0 2 2
5 5 7 7
8 8 10 10

2
-1