推箱子是一个很经典的游戏。今天我们来玩一个简单版本。在一个M*N的房间里有一个箱子和一个搬运工，搬运工的工作就是把箱子推到指定的位置,注意，搬运工只能推箱子而不能拉箱子，因此如果箱子被推到一个角上那么箱子就不能再被移动了，如果箱子被推到一面墙上，那么箱子只能沿着墙移动。

现在给定房间的结构，箱子的位置，搬运工的位置和箱子要被推去的位置，请你计算出搬运工至少要推动箱子多少格。

输入格式： 输入数据的第一行是一个整数T(1<=T<=20)，代表测试数据的数量。然后是T组测试数据，每组测试数据的第一行是两个正整数M,N(2<=M,N<=7)，代表房间的大小，然后是一个M行N列的矩阵，代表房间的布局，其中0代表空的地板，1 代表墙，2 代表箱子的起始位置，3 代表箱子要被推去的位置，4 代表搬运工的起始位置。

输出格式： 对于每组测试数据，输出搬运工最少需要推动箱子多少格才能帮箱子推到指定位置，如果不能推到指定位置则输出 -1。

样例输入： 1 5 5 0 3 0 0 0 1 0 1 4 0 0 0 1 0 0 1 0 2 0 0 0 0 0 0 0 样例输出： 4

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
struct Q{
	int x,y,p;
};
int n,m,t,s,S,e,E,c,d[4]={0,1,0,-1},D[4]={1,0,-1,0},a[8][8],z,Z;
bool v[115][115];
bool b(Q _)
{
	queue <Q> q;
	Q r;
	bool v[105][105]={};
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]==4)
			{
				r.x=i;
				r.y=j;
				r.p=0;
				goto A;
			}
		}		
	}
	A:;
	q.push(r);
	v[r.x][r.y]=1;
	while(!q.empty())
	{
		Q u=q.front();
		if(u.x==z && u.y==Z)
			return 1;
		q.pop();
		for(int i=0;i<4;i++)
		{
			int X=u.x+d[i],Y=u.y+D[i];        
			if(X && Y && X<=n && Y<=m && !v[X][Y] && a[X][Y]!=1 && a[X][Y]!=2)
			{
				v[X][Y]=1;				
				q.push({X,Y,u.p+1});
			}
		}
	}
	return 0;
}
void B()
{
	queue <Q> q;
	v[s][S]=1;
	q.push({s,S,0});
	memset(v,0,sizeof(v));
	while(!q.empty())
	{
		Q u=q.front();
		if(a[u.x][u.y]==3)
        {
			cout<<u.p<<"\n";
			return ;
		}  
		q.pop();
		for(int i=0;i<4;i++)
		{
			int X=u.x+d[i],Y=u.y+D[i];
			if(X && Y && X<=n && Y<=m && !v[X][Y] && a[X][Y]!=1)
			{
				z=u.x-d[i];
				Z=u.y-D[i];
				if(z && Z && z<=n && Z<=m)
				{         
                    if(b({z,Z,u.p+1}))
					{                       
                        v[X][Y]=1;                                         
                        q.push({X,Y,u.p+1});
                    }
				}
			}
		}
	}
	cout<<-1<<"\n";
}
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				cin>>a[i][j];
				if(a[i][j]==2)
				{
					s=i;
					S=j;
				}
				if(a[i][j]==3)
				{
					e=i;
					E=j;
				}
			}							
		}
		B();
	}
	return 0;
}