298

#include <iostream>
#include <cstdio>
#include <queue>
#include <sstream>
#include <string>
#include <cstring>
#include <cmath>

using namespace std;

bool gr[30][30][7][7];
//bool gr2D[30][30];

struct Point{
	int x,y,velocity,accleration;
	int val;
};
Point St,Fn;
int m,n;

void bfs()
{
	int x,y,v,a,val;
	int dx,dy,tx,ty;
	queue<int> q;
	q.push(St.x);q.push(St.y);
	q.push(0);q.push(0);q.push(0);
	gr[St.x][St.y][0+3][0+3]=1;

	while(!q.empty())
	{
		x=q.front();q.pop();
		y=q.front();q.pop();
		v=q.front();q.pop();
		a=q.front();q.pop();
		val = q.front();q.pop();
		//cout<<x<<" "<<y<<" "<<v<<" "<<a<<" "<<val<<"\n";
		if(x==Fn.x && y ==Fn.y)
		{
			printf("Optimal solution takes %d hops.\n", val);
			return;
		}
		for(int i=-1;i<=1;i++)
			for(int j=-1;j<=1;j++)
			{
				tx = v+i; ty = a+j;
				if(abs(tx)<=3 && abs(ty)<=3)
				{
					dx = x+v+i; dy = y+a+j;
					if(dx>=0 && dx<m && dy>=0 && dy<n && gr[dx][dy][tx+3][ty+3]==0)
					{
						//if(gr2D[dx][dy])
						//continue;
						gr[dx][dy][tx+3][ty+3]=1;
						q.push(dx); q.push(dy); q.push(tx); q.push(ty);
						q.push(val+1);
					}
				}
			}
	}
	printf("No solution.\n");
}

int main()
{
	int t,p;
	scanf("%d",&t);
	int x1,x2,y1,y2;
	Point A,B;
	while(t--)
	{
		scanf("%d%d",&m,&n);
		memset(gr,0,sizeof(gr));
		//memset(gr,0,sizeof(gr2D));
		scanf("%d%d%d%d",&St.x,&St.y,&Fn.x,&Fn.y);
		scanf("%d",&p);
		bool flag=1;
		while(p--)
		{
			scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
			for(int i=x1;i<=x2;i++)
			{
				for(int j=y1;j<=y2;j++)
				{
					//gr2D[i][j]=1;
					for(int k=0;k<7;k++)
					{
						for(int l=0;l<7;l++)
						{
							gr[i][j][k][l]=1;
							if(i==Fn.x && j==Fn.y)
								flag=0;
						}
					}
				}
			}
		}
		if(St.x==Fn.x && St.y==Fn.y)
		printf("Optimal solution takes 0 hops.\n");
		else
		{
			if(flag==0)
			printf("No solution.\n");
			else
			bfs();
		}
	}
	return 0;
}