Finding a Path

TooDee is a region on the $2$-dimensional Cartesian plane, home to the Dees: clever, bee-like $2$-dimensional creatures. TooDee contains beehives, and each beehive is a rectangle whose sides are all parallel to the coordinate axes.

A Dee may fly only according to fixed rules. Every flight path is made of axis-parallel (horizontal or vertical) segments whose endpoints all have integer coordinates. Every point discussed in TooDee has integer coordinates, and the flight rules are as follows.

• From the current point $(x, y)$, a Dee may move to one of the four neighbouring points $(x+1, y)$, $(x-1, y)$, $(x, y+1)$, $(x, y-1)$.
• A Dee may never enter the interior of a beehive (staying on a beehive's edge or corner is allowed).
• A Dee may change its flying direction only while on a beehive's edge or corner.
• At the start, a Dee may freely choose one of the four directions.

Tonight is the birthday of the daughter of Deeficer, TooDee's welfare officer, so Deeficer wants to get home from the office as quickly as possible. A Dee travels a length of $1$ per second. Obeying the rules above, find the minimum time in seconds to reach home from the office.

The first line contains the number of test scenarios $T$ ($1 \le T \le 20$). Then $T$ scenarios follow, each preceded by a single blank line.

The first line of each scenario contains four integers: the first two are the $x$ and $y$ coordinates of the office, and the last two are the $x$ and $y$ coordinates of home. The second line contains the number of beehives $N$. Each of the next $N$ lines describes one beehive by the coordinates of two diagonally opposite corners of its rectangle (four integers).

No two beehives overlap, share an edge, or touch at a corner. The office and home are at different locations, and every beehive has area at least $1$.

All coordinate values are between $-10^9$ and $10^9$ inclusive, and $0 \le N \le 1000$.

For each scenario, print on its own line the minimum time in seconds to fly from the office to home. If home cannot be reached while obeying the flight rules, print No Path.