#include <cstdio> #include <cstring> #include <iostream> #include <queue> #include <algorithm> using namespace std; const int N=10; int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; int map[N][N],vis[N][N][100]; int n,m,sx,sy,ex,ey,ans; struct node{ int x,y,step,t,init; node() {} node(int a, int b, int c, int d, int e): x(a), y(b), step(c), t(d), init(e) {} }; bool check(int x, int y){ if(x>=1 && x<=n && y>=1 && y<=m) return 1; return 0; } void bfs() { queue<node> v; node a; int i,px,py; v.push( node(sx,sy,0,0,0) ); vis[sx][sy][0]=1; while( !v.empty() ) { a=v.front(); v.pop(); // cout<<a.x<<" "<<a.y<<" "<<a.step<<" "<<a.t<<endl; if( a.t>=6 ) continue; if( a.x==ex && a.y==ey ){ ans=a.step; return; } for(i=0;i<4;i++){ px=a.x+dir[i][0]; py=a.y+dir[i][1]; if( map[px][py] && check(px,py) && !vis[px][py][a.init] ) { if( map[px][py]==1 ){ vis[px][py][a.init]=1; v.push( node(px,py,a.step+1,a.t+1,a.init) ); } else if( map[px][py]==4 && a.t+1<6 ){ vis[px][py][a.init]=1; v.push( node(px,py,a.step+1,0,a.init+1) ); } else if( map[px][py]==3 ){ vis[px][py][a.init]=1; v.push( node(px,py,a.step+1,a.t+1,a.init) ); } } } } ans=-1; } int main() { // freopen("in","r",stdin); // freopen("out","w",stdout); int i,r,t; scanf("%d",&t); while( t-- ) { memset(map,0,sizeof(map)); memset(vis,0,sizeof(vis)); scanf("%d%d",&n,&m); for(i=1;i<=n;i++) for(r=1;r<=m;r++) { scanf("%d",&map[i][r]); if( map[i][r]==2){ sx=i, sy=r; } else if( map[i][r]==3){ ex=i, ey=r; } } bfs(); printf("%d\n",ans); } return 0; }