Hoppers

Hoppers are people on pogo-style jump sticks who leap from one square to another, flying over the squares in between (much like a knight in chess). They can build up speed to make longer hops, but their acceleration each move is limited and they have a maximum speed.

The game of Hoppers is played on a rectangular grid. Each square is either empty or occupied. A hopper may fly over any square, but may only land on an empty square.

At any moment a hopper has a velocity $(x, y)$, where $x$ and $y$ are the speeds (in squares) along the two grid axes. For example, a velocity of $(2, 1)$ is a knight's move (as are $(-2, 1)$ and its six other reflections).

On each hop the hopper first adjusts its velocity, then moves by the new velocity. Each velocity component may change by $-1$, $0$, or $+1$. So from velocity $(2, 1)$ the hopper can switch to any of $(1,0)$, $(1,1)$, $(1,2)$, $(2,0)$, $(2,1)$, $(2,2)$, $(3,0)$, $(3,1)$, $(3,2)$. Neither component can ever reach a magnitude of $4$, so each component always stays in the range $-3$ to $3$ inclusive.

The goal is to travel from a start square $S$ to a finish square $F$ in as few hops as possible, never landing on an occupied square. A hopper begins at rest with velocity $(0, 0)$, and its velocity upon arriving at $F$ does not matter. Squares the hopper flies over may be occupied; only the squares it lands on must be empty.

Write a program that, given the grid, the start square, and the finish square, reports the minimum number of hops needed to get from $S$ to $F$.

The first line contains the number of test cases $N$.

Each test case has the following form:

• A line with the grid width $X$ ($1 \le X \le 16$) and height $Y$ ($1 \le Y \le 16$).
• A line with four integers $x_1$ $y_1$ $x_2$ $y_2$: the start square $(x_1, y_1)$ and the finish square $(x_2, y_2)$, both valid grid squares ($0 \le x_1, x_2 < X$ and $0 \le y_1, y_2 < Y$).
• A line with an integer $P$, the number of obstacle rectangles.
• $P$ lines, each describing one obstacle as four integers $x_1$ $x_2$ $y_1$ $y_2$ ($0 \le x_1 \le x_2 < X$, $0 \le y_1 \le y_2 < Y$). Every square $(x, y)$ with $x_1 \le x \le x_2$ and $y_1 \le y \le y_2$ is occupied.

The start and finish squares are never occupied.

For each test case, print one line.

If the hopper cannot reach the finish square from the start square without landing on an occupied square, print:

No solution.

Otherwise print:

Optimal solution takes N hops.

where N is the minimum number of hops required.