Hoppers

호퍼(hopper)는 장대에 올라탄 채 한 칸에서 다른 칸으로 뛰어다니는 사람이다. 중간 칸들은 건드리지 않고 뛰어넘는데, 체스의 나이트와 비슷하다. 속도를 붙여 더 멀리 뛸 수 있지만, 한 번에 바꿀 수 있는 가속에는 한계가 있고 최대 속도도 정해져 있다.

Hoppers 게임은 직사각형 격자판 위에서 진행된다. 각 칸은 비어 있거나 막혀 있다. 호퍼는 어떤 칸이든 위로 뛰어넘을 수 있지만, 착지는 빈 칸에만 할 수 있다.

임의의 순간에 호퍼는 속도 $(x, y)$ 를 가진다. 여기서 $x$ 와 $y$ 는 각각 격자의 두 축 방향으로 한 번에 이동하는 칸 수이다. 예를 들어 속도 $(2, 1)$ 은 나이트의 이동에 해당한다($(-2, 1)$ 등 나머지 6가지 대칭 이동도 마찬가지다).

각 도약에서 호퍼는 먼저 속도를 조정한 뒤, 새 속도만큼 이동한다. 속도의 각 성분은 $-1$, $0$, $+1$ 중 하나만큼 바뀔 수 있다. 따라서 속도 $(2, 1)$ 에서는 $(1,0)$, $(1,1)$, $(1,2)$, $(2,0)$, $(2,1)$, $(2,2)$, $(3,0)$, $(3,1)$, $(3,2)$ 중 하나로 바꿀 수 있다. 어느 성분도 절댓값 $4$ 에 도달할 수 없으므로, 각 성분은 항상 $-3$ 이상 $3$ 이하이다.

목표는 시작 칸 $S$ 에서 도착 칸 $F$ 까지, 막힌 칸에 착지하지 않으면서 가능한 한 적은 도약 횟수로 이동하는 것이다. 호퍼는 속도 $(0, 0)$ 인 정지 상태에서 출발하며, $F$ 에 도착할 때의 속도는 상관없다. 뛰어넘는 칸은 막혀 있어도 되고, 착지하는 칸만 비어 있으면 된다.

격자판과 시작 칸, 도착 칸이 주어질 때 $S$ 에서 $F$ 까지 필요한 최소 도약 횟수를 구하는 프로그램을 작성하라.

첫째 줄에 테스트 케이스의 수 $N$ 이 주어진다.

각 테스트 케이스는 다음과 같이 구성된다.

• 격자의 너비 $X$ ($1 \le X \le 16$) 와 높이 $Y$ ($1 \le Y \le 16$) 가 주어지는 줄.
• 네 정수 $x_1$ $y_1$ $x_2$ $y_2$ 가 주어지는 줄. 앞의 두 수는 시작 칸 $(x_1, y_1)$, 뒤의 두 수는 도착 칸 $(x_2, y_2)$ 를 나타내며, 둘 다 격자 안의 유효한 칸이다($0 \le x_1, x_2 < X$, $0 \le y_1, y_2 < Y$).
• 장애물 직사각형의 개수 $P$ 가 주어지는 줄.
• 이어서 $P$ 개의 줄. 각 줄은 네 정수 $x_1$ $x_2$ $y_1$ $y_2$ ($0 \le x_1 \le x_2 < X$, $0 \le y_1 \le y_2 < Y$) 로 하나의 장애물을 나타낸다. $x_1 \le x \le x_2$ 이고 $y_1 \le y \le y_2$ 인 모든 칸 $(x, y)$ 가 막혀 있다.

시작 칸과 도착 칸은 절대 막혀 있지 않다.

각 테스트 케이스마다 한 줄을 출력한다.

호퍼가 막힌 칸에 착지하지 않고서는 시작 칸에서 도착 칸에 도달할 수 없다면 다음을 출력한다.

No solution.

그렇지 않으면 다음을 출력한다.

Optimal solution takes N hops.

여기서 N 은 필요한 최소 도약 횟수이다.