#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<queue>

using namespace std;

const int INF=10e8;

const int MAXN=55;

int col,row,k,minn;

char str[MAXN][MAXN];

int maze[MAXN][MAXN],dist[MAXN*2][MAXN*2],lowdis[MAXN*2];

int dx[]={-1,0,0,1};

int dy[]={0,-1,1,0};

bool vist[MAXN][MAXN]; //BFS时记录是否走过

bool vis[MAXN*2];

struct Node

{

    int x,y;

    int dis;

}node[MAXN*2];

bool judge(int x,int y)

{//判断是否过界，或者是否能继续查下去

    if(x<0||x>=row||y<0||y>=col||maze[x][y]==-1||vist[x][y]==1)

        return false;

    return true;

}

void BFS(int n)//用bfs建立邻接矩阵

{

    queue<Node> que; //que为Node型的队列变量

    memset(dist,0,sizeof(dist));

    Node u,next; //u用来保存当前的队列元素，next保存下一个队列元素

    for(int i=1;i<=n;i++)

    {

        while(!que.empty())

            que.pop(); //清空队列元素

        memset(vist,0,sizeof(vist));

        int tot=0;

        node[i].dis=0;

        vist[node[i].x][node[i].y]=1;

        que.push(node[i]);

        while(!que.empty())

        {

            u=que.front();que.pop();

            int x=u.x,y=u.y;

            if(maze[x][y]!=0&&maze[x][y]!=-1)

            {

                tot++;

                dist[i][maze[x][y]]=dist[maze[x][y]][i]=u.dis;

                if(tot==n) break;

            }

            for(int j=0;j<4;j++) //从u点的四个方向上查找

            {

                int xx=u.x+dx[j],yy=u.y+dy[j];

                if(judge(xx,yy))

                {

                    next.x=xx;next.y=yy;

                    next.dis=u.dis+1;

                    vist[xx][yy]=1;

                    que.push(next);

                }

            }

        }

    }

}

int Prim(int n)

{

    int ans=0;

    memset(vis,0,sizeof(vis));

    vis[1]=1;

    for(int i=1;i<=n;i++)

        lowdis[i]=dist[1][i];

    for(int i=1;i<=n-1;i++)

    {

        minn=INF;k=-1;

        for(int j=1;j<=n;j++)

        {

            if(!vis[j]&&minn>lowdis[j])

            {

                minn=lowdis[j];

                k=j;

            }

        }

        if(k==-1) break;

        ans+=minn;vis[k]=1;

        for(int j=1;j<=n;j++)

            if(!vis[j]&&lowdis[j]>dist[k][j])

                lowdis[j]=dist[k][j];

    }

    return ans;

}

int main()

{

    int n;

    scanf("%d",&n);

    while(n--)

    {

        int cnt=0;

        memset(node,0,sizeof(node));

        scanf("%d%d",&col,&row);

        char ch[MAXN];

        gets(ch);//重点！处理输入时多余的空格

        for(int i=0;i<row;i++)

        {

            gets(str[i]);

            for(int j=0;j<col;j++)

                if(str[i][j]=='A'||str[i][j]=='S')

                {

                    cnt++;

                    maze[i][j]=cnt;

                    node[cnt].x=i,node[cnt].y=j;

                }

                else if(str[i][j]==' ')

                    maze[i][j]=0;

                else if(str[i][j]=='#')

                    maze[i][j]=-1;

        }

        BFS(cnt);

        printf("%d\n",Prim(cnt));

    }

    return 0;

}