#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

#define MAXN 110
#define MAXM 10010

int r,c;
int pnx[MAXN],pny[MAXN],dis[55][55],vis[55][55],num;
int uu[MAXM],vv[MAXM],ww[MAXM],et;
char map[55][55];
int fa[MAXN],nr[MAXM];

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

void bfs(int k)
{
    memset(vis,0,sizeof(vis));
    queue<int> q;
    int u,v;
    int x,y,nx,ny;
    x = pnx[k];
    y = pny[k];
    u = x*c+y;
    dis[x][y] = 0;
    vis[x][y] = 1;
    q.push(u);
    while(!q.empty()){
        u = q.front();
        q.pop();
        x = u/c;
        y = u%c;
        for(int i=0;i<4;i++){
            nx = x+dx[i];
            ny = y+dy[i];
            if(nx>=0&&ny>=0&&nx<r&&ny<c&&!vis[nx][ny]&&map[nx][ny]!='#'){
                v = nx*c+ny;
                q.push(v);
                vis[nx][ny] = 1;
                dis[nx][ny] = dis[x][y]+1;
            }
        }
    }
}

int find(int x)
{
    return x==fa[x]? x:fa[x]=find(fa[x]);
}

int cmp(int a,int b)
{
    return ww[a]<ww[b];
}

int Kruskal()
{
    for(int i=0;i<num;i++) fa[i]=i;
    for(int i=0;i<et;i++) nr[i]=i;
    sort(nr,nr+et,cmp);
    int ans = 0;
    for(int i=0;i<et;i++){
        int e = nr[i];
        int x = find(uu[e]);
        int y = find(vv[e]);
        if(x!=y){
            ans += ww[e];
            fa[y] = x;
        }
    }
    return ans;
}

int main()
{
    //freopen("input.in","r",stdin);
    int cas;
    scanf("%d",&cas);
    while(cas--){
        scanf("%d%d",&c,&r);
        char tmp[115];gets(tmp);
        for(int i=0;i<r;i++){
            gets(map[i]);
        }
        num = 0;
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                if(map[i][j]=='A'||map[i][j]=='S'){
                    pnx[num] = i;
                    pny[num++] = j;
                }
            }
        }
        et = 0;
        for(int i=0;i<num;i++){
            memset(dis,0,sizeof(dis));
            bfs(i);
            for(int j=i+1;j<num;j++){
                uu[et] = i;
                vv[et] = j;
                ww[et++] = dis[pnx[j]][pny[j]];
            }
        }
        int res = Kruskal();
        printf("%d\n",res);
    }
    return 0;
}