#include<iostream>
#include<cmath>
#include<queue>
#define MAX 200
#define INT_MAX 1<<20
using namespace std;
struct Point
{
   int x,y;
   int level;
};
int m,n,t;
char input[MAX][MAX];
int move[4][2]={0,1,0,-1,1,0,-1,0};
int dist(Point u,Point v)
{
   int i,j;
   bool visit[MAX][MAX];
   for(i=0;i<=m+1;i++)
   {
      for(j=0;j<=n+1;j++)
      {
         visit[i][j]=false;
      }
   }
   Point now,tmp;
   u.level=0;
   queue<Point> Q;
   Q.push(u);
   visit[u.x][u.y]=true;
   while(!Q.empty())
   {
      now=Q.front();
      if(now.x==v.x&&now.y==v.y)
      {
         return now.level;
      }
      Q.pop();
      for(i=0;i<4;i++)
      {
         tmp.x=now.x+move[i][0];
         tmp.y=now.y+move[i][1];
         tmp.level=now.level+1;
         if(!visit[tmp.x][tmp.y]&&input[tmp.x][tmp.y]!='#')
         {
            visit[tmp.x][tmp.y]=true;
            Q.push(tmp);
         }
      }
   }   
}
int main()
{
   int val[MAX][MAX];
   bool visited[MAX];
   Point p[MAX];
   int lowcost[MAX];
   int min;
   int sum;
   int closest;
   int i,j;
   cin>>t;
   while(t--)
   {
      sum=0;
      cin>>n>>m;
      cin.get();
      int location=2;
      for(i=0;i<=m+1;i++)
      {
         input[i][0]='#';
         input[i][n+1]='#';
      }
      for(i=0;i<=n+1;i++)
      {
         input[0][i]='#';
         input[m+1][i]='#';
      }
      for(i=1;i<=m;i++)
      {
         for(j=1;j<=n;j++)
         {
            input[i][j]=cin.get();
            if(input[i][j]=='S')
            {
               p[1].x=i;
               p[1].y=j;
            }
         }
         cin.get();
      }
      /*for(i=0;i<=m+1;i++)
      {
         for(j=0;j<=n+1;j++)
         {
            cout<<input[i][j];
         }
         cout<<endl;
      }*/
      for(i=1;i<=m;i++)
      {
         for(j=1;j<=n;j++)
         {
            if(input[i][j]=='A')
            {
               p[location].x=i;
               p[location++].y=j;
            }
         }
      }
      for(i=1;i<location;i++)
      {
         visited[i]=false;
      }
      for(i=1;i<location;i++)
      {
         for(j=i;j<location;j++)
         {
            val[i][j]=dist(p[i],p[j]);
            val[j][i]=val[i][j];
         }
      }
      for(i=1;i<location;i++)
      {
         for(j=1;j<location;j++)
         {
            cout<<val[i][j]<<" ";
         }
         cout<<endl;
      }
      visited[1]=true;
      for(i=1;i<location;i++)
      {
         lowcost[i]=val[i][1];
      }
      for(i=1;i<location-1;i++)
      {
         min=INT_MAX;
         for(j=1;j<location;j++)
         {
            if(!visited[j]&&lowcost[j]<min)
            {
               min=lowcost[j];
               closest=j;
            }
         }
         visited[closest]=true;
         sum+=min;
         for(j=1;j<location;j++)
         {
            if(!visited[j]&&lowcost[j]>val[closest][j])
            {
               lowcost[j]=val[closest][j];
            }
         }
      }
      cout<<sum<<endl;
   }
   return 0;
}