UVA298 Race Tracks

许多学生在无聊的数学课上玩赛车游戏。 两个玩家在纸上画的赛道上操纵他们的赛车，而他们的赛车初始速度为 $(0,0)$，可以进行加速（可以使正数或负数）。赛道上，赛车可以进行跳跃。 他们可以从一个格子跳到另一个格子，而不会碰到中间的格子（有点像国际象棋中的骑士）。就像前面提到的赛车一样，赛车可以改变速度并做出更大的跳跃，但是它们改变速度是有限制的。 让我们更正式一点：我们的赛车游戏是在矩形网格上进行的，其中网格上的每个格子都为空或已被覆盖。赛车可以飞越格子，但只能落在空的格子上。 在任何时间点，赛车的速度是 $(x,y)$，其中 $x,y$ 是赛车飞越格子的速度（以格子数量为单位）。因此，$(2,1)$ 的速度对应于骑士的跳跃的速度。 要知道赛车可以跳多远，我们需要知道他增加或者减少多少速度：对于 $x,y$ 他只能加 $1$，减 $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$之间。 至少跳多少步，赛车才能到达终点？。 您将编写一个程序，给定一个矩形网格，一个起点 $S$ 和一个终点 $F$，该程序确定从 $S$ 到 $F$ 的最少需要跳多少次。 赛车初始速度为 $(0,0)$ 当他到达 $F$ 时，他的速度忽略不计。

第一行包含测试数据组数 $N$。 每个测试数据包含网格的 长 $X$，和宽 $Y$。 接下来一行包含用空格分隔开的四个整数。 前两个表示起点 $(x1,y1)$,后两个表示终点 $(x2,y2)$。 接下来一行是一个整数 $P$，是指障碍物的数量。 接下来 $P$ 行，每行四个整数 $(x1,x2,y1,y2)$，表示障碍物的四个端点，该区域内的空格被覆盖。 起点永远不会被覆盖。

每个测试数据的答案占一行。 如果赛车无法到达终点，就输出 “No solution.”（不包含引号）。 如果可以，就输出需要跳跃的最少次数。 ## 数据规模 $ 1\le X\le30$，$1\le Y\le30$。 $0\le x_1\le x_2