#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
char arr[1010][1010];
int vis[1010][1010];
int dist[1010][1010];
int dr[]={1,0,-1,0};
int dc[]={0,1,0,-1};
int n, m;
int safe(int x,int y)
{
return x>=0 && y>=0 && x<n && y<m;
}
void bfs(int sx, int sy)
{
queue< pii >q;
q.push(pii(sx,sy));
vis[sx][sy]=1;
dist[sx][sy]=1;
while(!q.empty())
{
pii top=q.front();
q.pop();
for(int i=0; i<4; i++)
{
int a = top.first + dr[i];
int b = top.second + dc[i];
if(safe(a,b) && !dist[a][b] && (int)arr[a][b]!=(int)arr[top.first][top.second])
{
q.push(pii(a,b));
dist[a][b] = dist[top.first][top.second]+1;
vis[a][b]=1;
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
int tc;
cin>>tc;
while(tc--)
{
cin>>n>>m;
memset(arr,0,sizeof(arr));
memset(vis, 0, sizeof(vis));
memset(dist, 0, sizeof(dist));
for(int i=0; i<n; i++)
{
cin>>arr[i];
}
bfs(0,0);
if(!vis[n-1][m-1])
cout<<"-1\n";
else
cout<<dist[n-1][m-1]<<endl;
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBwaWkgcGFpcjxpbnQsaW50PgpjaGFyIGFyclsxMDEwXVsxMDEwXTsKIAppbnQgdmlzWzEwMTBdWzEwMTBdOwppbnQgZGlzdFsxMDEwXVsxMDEwXTsKIAppbnQgZHJbXT17MSwwLC0xLDB9OwppbnQgZGNbXT17MCwxLDAsLTF9OwogCmludCBuLCBtOwogCmludCBzYWZlKGludCB4LGludCB5KQp7CiAgcmV0dXJuIHg+PTAgJiYgeT49MCAmJiB4PG4gJiYgeTxtOwp9CiAKIAp2b2lkIGJmcyhpbnQgc3gsIGludCBzeSkKewoJcXVldWU8IHBpaSA+cTsKCXEucHVzaChwaWkoc3gsc3kpKTsKIAogICAgdmlzW3N4XVtzeV09MTsKICAgIGRpc3Rbc3hdW3N5XT0xOwogCgl3aGlsZSghcS5lbXB0eSgpKQoJewoJCXBpaSB0b3A9cS5mcm9udCgpOwoJCXEucG9wKCk7CgkJZm9yKGludCBpPTA7IGk8NDsgaSsrKQoJCXsKCQkJaW50IGEgPSB0b3AuZmlyc3QgKyBkcltpXTsKCQkJaW50IGIgPSB0b3Auc2Vjb25kICsgZGNbaV07CiAKICAgICAgICAgICAgaWYoc2FmZShhLGIpICYmICFkaXN0W2FdW2JdICYmIChpbnQpYXJyW2FdW2JdIT0oaW50KWFyclt0b3AuZmlyc3RdW3RvcC5zZWNvbmRdKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgIHEucHVzaChwaWkoYSxiKSk7CiAgICAgICAgICAgICAgIGRpc3RbYV1bYl0gPSBkaXN0W3RvcC5maXJzdF1bdG9wLnNlY29uZF0rMTsKICAgICAgICAgICAgICAgdmlzW2FdW2JdPTE7CiAgICAgICAgICAgIH0KCQl9Cgl9Cn0KIAogCmludCBtYWluKCkKewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgaW50IHRjOwogCiAgICBjaW4+PnRjOwogICAgd2hpbGUodGMtLSkKICAgIHsKICAgICAgICBjaW4+Pm4+Pm07CiAKICAgICAgICBtZW1zZXQoYXJyLDAsc2l6ZW9mKGFycikpOwogICAgICAgIG1lbXNldCh2aXMsIDAsIHNpemVvZih2aXMpKTsKICAgICAgICBtZW1zZXQoZGlzdCwgMCwgc2l6ZW9mKGRpc3QpKTsKIAogICAgICAgIGZvcihpbnQgaT0wOyBpPG47IGkrKykKICAgICAgICB7CiAgICAgICAgICBjaW4+PmFycltpXTsKICAgICAgICB9CiAgICAgICAgYmZzKDAsMCk7CiAgICAgICAgaWYoIXZpc1tuLTFdW20tMV0pCiAgICAgICAgICAgIGNvdXQ8PCItMVxuIjsKICAgICAgICBlbHNlCiAgICAgICAgICAgIGNvdXQ8PGRpc3Rbbi0xXVttLTFdPDxlbmRsOwogICAgfQogICAgcmV0dXJuIDA7Cn0KIAo=