Input file: hop.in
Output file: hop.out

　　单足跳者是一个站在弹棒上人，他能从一个格子弹跳到另一格子（脚不触地）。他们可以加大跳跃的速率（X，Y方向的增量），从而做更大的跳跃。但他每次的移动的速率是有限的，即他们有一个最大的速率。这个单足跳者的游戏是在一个矩形栅格中进行，栅格中的格子要么空的，要么被障碍占有了。单足跳者可以跳过任意的格子，但他只能落在一个空的格子中。在任意的格子中，单足跳者有一个速率（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的速率，于是X和Y的值位于[-3，3]之间。在每一次跳动前，单足跳者都可以改变跳动的速率，例如当前的位置在（1，1）时他的速率为（1，1），他可改变速率为（2，0），且跳至（3，1）。

　　单足跳者的目的是从尽可能快从起始位置到终点（即以最少的跳跃），且不能着陆在任一有障碍的格子中。请你编写一个程序，对于给定一个矩形栅格，及起点S和终点.F，算出从S到F最少跳动次数，初始时这个单足跳者的速率为（0，0），且不必关心到达F时的速率。

　　输入要求：

　　输入文件的第一行包含一个要处理的测试情况数目，对于每一组测试数据的第一行为栅格的宽度X(1 <= X <= 16)和高度Y (1 <= Y <= 16)，接着一行是四个（空格隔开）的整数，表示起始点坐标(x1,y1) 和终点坐标(x2,y2)，（0 <= x1 < X, 0 <= x2 < X, 0 <= y1 < Y, and 0 <= y2 < Y)。第三行包含一个整数P代表栅格中的障碍的数目，该测试数据的最后包含P行，每行指定一个障碍，每个障碍包含4个整数x1, x2, y1 和y2, (0 <= x1 <= x2 < X, 0 <= y1 <=
y2 < Y), 代表所有的格子(x,y)，其中 x1 <= x <= x2 and y1 <= y <= y2，是被占有的。（注：起点和终点都不可能被占有）。

　　输出要求：

　　若单足跳者没有从起点到终点的路，则输出"No solution."，否则输出'Optimal solution takes N hops.'，其中N是跳跃的步数。

　　Sample input

　　2
　　5 5
　　4 0 4 4
　　1
　　1 4 2 3
　　3 3
　　0 0 2 2
　　2
　　1 1 0 2
　　0 2 1 1

　　Sample output

　　Optimal solution takes 7 hops.
　　No solution.

　　输入实例的说明

　　输入例子可以说明如下：#号代表被占有的格子，S代表起点，F代表终点，*表示栅格的边界，那么以上的例可以表示如下：

　　2
　　5 5
　　*******
　　* F*
　　* ####*
　　* ####*
　　* *
　　* S*
　　*******
　　3 3
　　*****
　　* #F*
　　*###*
　　*S# *
　　*****