#include <bits/stdc++.h>
using namespace std;
class help{
public:
int r;
int c;
int depth;
help(int row,int col,int depth)
{
this->r=row;
this->c=col;
this->depth=depth;
}
};
int main() {
int t;
cin>>t;
while(t–)
{
int r_index[]={0,0,-1,1};
int c_index[]={1,-1,0,0};
int r;
int c;
cin>>r>>c;
int** arr = new int*[r];
for (int i = 0; i < r; i++) {
arr[i] = new int[c];
}
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
cin>>arr[i][j];
}
}
queue<help> q;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
if(arr[i][j]==2)
{
help y(i,j,0);
q.push(y);
}
}
}
int ans=0;
while(!q.empty())
{
help x=q.front();
q.pop();
int row=x.r;
int col=x.c;
int depth=x.depth;
ans=max(ans,depth);
for(int i=0;i<4;i++)
{
int n_r=row+r_index[i];
int n_c=col+c_index[i];
if(n_r>=0 &&n_c>=0&&n_r<r&&n_c<c&&arr[n_r][n_c]==1)
{
help x(n_r,n_c,depth+1);
q.push(x);
}
}
}
bool flag=false;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
if(arr[i][j]==1)
{ cout<<"-1"<<endl;
flag=true;
break;
}
}
if(flag==true)
break;
}
if(flag==false)
{
cout<<ans<<endl;
}
}
// your code goes here
return 0;
}