#include <bits/stdc++.h>
using namespace std;
int BFS();
char grid[30][30];
int distances[30][30];
int r=0,c=0,s1=0,s2=0,f1=0,f2=0;
int dx[]={1,-1,0,0};
int dy[]={0,0,-1,1};
set<pair<int,int>> points;//Keeps track of points
int main()
{
ios_base::sync_with_stdio(false);//FAST IO
int t;
cin>>t;
while(t--)
{
points.clear();//clearing set
cin>>r;//rows columns
c=r;
for(int i=0;i<r;i++)
{
string x1;
cin>>x1;
for(int j=0;j<c;j++)
{
grid[i][j]=x1[j];
distances[i][j]=-1;
if(x1[j]=='*')//Found treasures
{
pair<int, int>tmp=make_pair(i,j);
points.insert(tmp);//adding treasures to set
}
}
}//built grid
s1=s2=0;
distances[s1][s2]=0;//for 0,0
int ansd=0;
int flag=1;
while(!points.empty())//Till treasures no more
{
for(int i=0;i<r;i++)
{
for (int j = 0; j < c; j++)//reseting
{
distances[i][j]=-1;
if(grid[i][j]=='V')//Visited
{
grid[i][j]='.';//Accesibly again in next walk
}
}
}
distances[s1][s2]=0;//next source specified in BFS function
int dis=BFS();
if(dis!=-1)
{
ansd += dis;
}
else
{
cout<<"-1\n";
flag = 0;
break;
}
}
if(flag==1)//This means that all treasures collected. Applying BFS for (n,n)
{
for(int i11=0;i11<r;i11++)//resetting
{
for(int j1=0;j1<c;j1++)
{
if(grid[i11][j1]=='V')
{
grid[i11][j1]='.';
}
distances[i11][j1]=0;
}
}
f1=r-1;f2=c-1;
grid[f1][f2]='*';//setting destination as treasure itself
int x=BFS();
if(x!=-1)
{
cout<<(ansd+x)<<endl;
}
else
{
cout<<"-1\n";
}
}
}
return 0;
}
int BFS()
{
queue<pair<int,int>> q;//Queue for BFS
pair<int,int> src=make_pair(s1,s2);//source coordinates
q.push(src);
while(!q.empty())
{
pair<int,int> p=q.front();
q.pop();
for(int i=0;i<4;i++)
{
if(((p.first+dx[i]>=0)&&(p.first+dx[i]<r))&&((p.second+dy[i]>=0)&&(p.second+dy[i]<c))&&(grid[p.first+dx[i]][p.second+dy[i]]!='#'))
{//If point is in range and is valid
int cx,cy;
cx=p.first+dx[i];
cy=p.second+dy[i];
distances[cx][cy]=distances[p.first][p.second]+1;//Distances
if(grid[cx][cy]=='*')//destination
{
for(pair<int,int> rm:points)
{
if(rm.first==cx&&rm.second==cy)// Finding the node and removing it
{
points.erase(rm);
break;
}
}
grid[cx][cy]='.';//It is walkable again
s1=cx;s2=cy;//next source set
return distances[cx][cy];
}
else if(grid[cx][cy]=='.')//Normal tile. Now setting to visited
{
grid[cx][cy]='V';//Adding to visited
pair<int,int> temp=make_pair(cx,cy);
q.push(temp);
}
}
}
}
return -1;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgQkZTKCk7CgpjaGFyIGdyaWRbMzBdWzMwXTsKaW50IGRpc3RhbmNlc1szMF1bMzBdOwppbnQgcj0wLGM9MCxzMT0wLHMyPTAsZjE9MCxmMj0wOwppbnQgZHhbXT17MSwtMSwwLDB9OwppbnQgZHlbXT17MCwwLC0xLDF9OwoKc2V0PHBhaXI8aW50LGludD4+IHBvaW50czsvL0tlZXBzIHRyYWNrIG9mIHBvaW50cwoKaW50IG1haW4oKQp7Cglpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsvL0ZBU1QgSU8KCWludCB0OwoJY2luPj50OwoJd2hpbGUodC0tKQoJewoJCXBvaW50cy5jbGVhcigpOy8vY2xlYXJpbmcgc2V0CgkJY2luPj5yOy8vcm93cyBjb2x1bW5zCgkJYz1yOwoJCWZvcihpbnQgaT0wO2k8cjtpKyspCgkJewoJCQlzdHJpbmcgeDE7CgkJCWNpbj4+eDE7CgkJCWZvcihpbnQgaj0wO2o8YztqKyspCgkJCXsKCQkJCWdyaWRbaV1bal09eDFbal07CgkJCQlkaXN0YW5jZXNbaV1bal09LTE7CgkJCQlpZih4MVtqXT09JyonKS8vRm91bmQgdHJlYXN1cmVzCgkJCQl7CgkJCQkJcGFpcjxpbnQsIGludD50bXA9bWFrZV9wYWlyKGksaik7CgkJCQkJcG9pbnRzLmluc2VydCh0bXApOy8vYWRkaW5nIHRyZWFzdXJlcyB0byBzZXQKCQkJCX0KCQkJfQoJCX0vL2J1aWx0IGdyaWQKCQlzMT1zMj0wOwoJCWRpc3RhbmNlc1tzMV1bczJdPTA7Ly9mb3IgMCwwCgkJaW50IGFuc2Q9MDsKCQlpbnQgZmxhZz0xOwoJCXdoaWxlKCFwb2ludHMuZW1wdHkoKSkvL1RpbGwgdHJlYXN1cmVzIG5vIG1vcmUKICAgICAgICB7CiAgICAgICAgICAgIGZvcihpbnQgaT0wO2k8cjtpKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgYzsgaisrKS8vcmVzZXRpbmcgCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgZGlzdGFuY2VzW2ldW2pdPS0xOwogICAgICAgICAgICAgICAgICAgIGlmKGdyaWRbaV1bal09PSdWJykvL1Zpc2l0ZWQKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIGdyaWRbaV1bal09Jy4nOy8vQWNjZXNpYmx5IGFnYWluIGluIG5leHQgd2FsawogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBkaXN0YW5jZXNbczFdW3MyXT0wOy8vbmV4dCBzb3VyY2Ugc3BlY2lmaWVkIGluIEJGUyBmdW5jdGlvbgogICAgICAgICAgICBpbnQgZGlzPUJGUygpOwogICAgICAgICAgICBpZihkaXMhPS0xKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBhbnNkICs9IGRpczsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGNvdXQ8PCItMVxuIjsKICAgICAgICAgICAgICAgIGZsYWcgPSAwOwogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgaWYoZmxhZz09MSkvL1RoaXMgbWVhbnMgdGhhdCBhbGwgdHJlYXN1cmVzIGNvbGxlY3RlZC4gQXBwbHlpbmcgQkZTIGZvciAobixuKQogICAgICAgIHsKICAgICAgICAgICAgZm9yKGludCBpMTE9MDtpMTE8cjtpMTErKykvL3Jlc2V0dGluZwogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBmb3IoaW50IGoxPTA7ajE8YztqMSsrKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGlmKGdyaWRbaTExXVtqMV09PSdWJykKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIGdyaWRbaTExXVtqMV09Jy4nOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICBkaXN0YW5jZXNbaTExXVtqMV09MDsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBmMT1yLTE7ZjI9Yy0xOwogICAgICAgICAgICBncmlkW2YxXVtmMl09JyonOy8vc2V0dGluZyBkZXN0aW5hdGlvbiBhcyB0cmVhc3VyZSBpdHNlbGYKICAgICAgICAgICAgaW50IHg9QkZTKCk7CiAgICAgICAgICAgIGlmKHghPS0xKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBjb3V0PDwoYW5zZCt4KTw8ZW5kbDsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGNvdXQ8PCItMVxuIjsKICAgICAgICAgICAgfQogICAgICAgIH0KCX0KCXJldHVybiAwOwp9CgppbnQgQkZTKCkKewogICAgcXVldWU8cGFpcjxpbnQsaW50Pj4gcTsvL1F1ZXVlIGZvciBCRlMKICAgIHBhaXI8aW50LGludD4gc3JjPW1ha2VfcGFpcihzMSxzMik7Ly9zb3VyY2UgY29vcmRpbmF0ZXMKICAgIHEucHVzaChzcmMpOwogICAgd2hpbGUoIXEuZW1wdHkoKSkKICAgIHsKICAgICAgICBwYWlyPGludCxpbnQ+IHA9cS5mcm9udCgpOwogICAgICAgIHEucG9wKCk7CiAgICAgICAgZm9yKGludCBpPTA7aTw0O2krKykKICAgICAgICB7CiAgICAgICAgICAgIGlmKCgocC5maXJzdCtkeFtpXT49MCkmJihwLmZpcnN0K2R4W2ldPHIpKSYmKChwLnNlY29uZCtkeVtpXT49MCkmJihwLnNlY29uZCtkeVtpXTxjKSkmJihncmlkW3AuZmlyc3QrZHhbaV1dW3Auc2Vjb25kK2R5W2ldXSE9JyMnKSkKICAgICAgICAgICAgey8vSWYgcG9pbnQgaXMgaW4gcmFuZ2UgYW5kIGlzIHZhbGlkCiAgICAgICAgICAgICAgICBpbnQgY3gsY3k7CiAgICAgICAgICAgICAgICBjeD1wLmZpcnN0K2R4W2ldOwogICAgICAgICAgICAgICAgY3k9cC5zZWNvbmQrZHlbaV07CiAgICAgICAgICAgICAgICBkaXN0YW5jZXNbY3hdW2N5XT1kaXN0YW5jZXNbcC5maXJzdF1bcC5zZWNvbmRdKzE7Ly9EaXN0YW5jZXMKICAgICAgICAgICAgICAgIGlmKGdyaWRbY3hdW2N5XT09JyonKS8vZGVzdGluYXRpb24KICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBmb3IocGFpcjxpbnQsaW50PiBybTpwb2ludHMpCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBpZihybS5maXJzdD09Y3gmJnJtLnNlY29uZD09Y3kpLy8gRmluZGluZyB0aGUgbm9kZSBhbmQgcmVtb3ZpbmcgaXQKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgcG9pbnRzLmVyYXNlKHJtKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIGdyaWRbY3hdW2N5XT0nLic7Ly9JdCBpcyB3YWxrYWJsZSBhZ2FpbgogICAgICAgICAgICAgICAgICAgIHMxPWN4O3MyPWN5Oy8vbmV4dCBzb3VyY2Ugc2V0CiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIGRpc3RhbmNlc1tjeF1bY3ldOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZSBpZihncmlkW2N4XVtjeV09PScuJykvL05vcm1hbCB0aWxlLiBOb3cgc2V0dGluZyB0byB2aXNpdGVkCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgZ3JpZFtjeF1bY3ldPSdWJzsvL0FkZGluZyB0byB2aXNpdGVkCiAgICAgICAgICAgICAgICAgICAgcGFpcjxpbnQsaW50PiB0ZW1wPW1ha2VfcGFpcihjeCxjeSk7CiAgICAgICAgICAgICAgICAgICAgcS5wdXNoKHRlbXApOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIC0xOwp9