#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <queue>
#define GSIZE 52
#define NSIZE 105

using namespace std;

struct _node
{
    int y, x;
};

int n, x, y, ncount, map[NSIZE][NSIZE];
char graph[GSIZE][GSIZE];
struct _node node[NSIZE];
bool vst[GSIZE][GSIZE];

int pos(struct _node mynode)    //返回某字母的编号
{
    int i;
    for(i = 0; i < ncount; i++)
        if(node[i].y == mynode.y && node[i].x == mynode.x)
            return i;
    return -1;
}

bool isOK(int a, int b)
{
    if(a >= 0 && a < y && b >= 0 && b < x && graph[a][b] != '#' && !vst[a][b])
        return true;
    return false;
}

void bfs(int s)
{
    queue<struct _node> q;
    int floor = 0, cnt = 0; //floor宽度优先搜索数的层次，cnt记录已访问字母个数
    struct _node empty; //不可能存在的坐标，仅作为队列中的分层标记
    empty.y = empty.x = -1;
    memset(vst, 0, sizeof(vst));
    q.push(node[s]);
    vst[node[s].y][node[0].x] = true;
    q.push(empty);
    while(!q.empty())
    {
        struct _node tmp = q.front();
        q.pop();
        if(tmp.y == -1) //队首是分层标记
        {
            if(q.empty())
                return;
            else
            {
                floor++;    //层次增长
                q.push(empty);  //分隔下一层的元素
                continue;
            }
        }
        if(graph[tmp.y][tmp.x] == 'A' || graph[tmp.y][tmp.x] == 'S')
        {
            map[s][pos(tmp)] = floor;
            if(++cnt == ncount) //s到各个字母的路长都已找到
                return;
        }
        int i, dirc[4][2] = {{-1,0}, {0, 1}, {1, 0}, {0, -1}};
        for(i = 0; i < 4; i++)
            if(isOK(tmp.y + dirc[i][0], tmp.x + dirc[i][1]))
            {
                struct _node tt;
                tt.y = tmp.y + dirc[i][0];
                tt.x = tmp.x + dirc[i][1];
                q.push(tt);
                vst[tt.y][tt.x] = true;
            }
    }
    return;
}

int prim(int s)
{
    bool inq[NSIZE];
    int dist[NSIZE], count = 0, ret = 0;
    int i,j;
    for(i = 0; i < ncount; i++)
    {
        inq[i] = false;
        dist[i] = 0x7fffffff;
    }
    dist[s] = 0;
    while(count < ncount)
    {
        int min = 0x7fffffff;
        for(i = 0; i < ncount; i++)
            if(!inq[i] && min > dist[i])
            {
                min = dist[i];
                j = i;
            }
        inq[j] = true;
        count++;
        ret += dist[j];
        for(i = 0; i < ncount; i++)
            if(!inq[i] && dist[i] > map[j][i])
                dist[i] = map[j][i];
    }
    return ret;
}

int main()
{
    scanf("%d", &n);
    while(n--)
    {
        scanf("%d%d", &x, &y);
        int i, j;
        ncount = 0; //字母个数
        char str[100];
        gets(str);
        for(i = 0; i < y; i++)
        {
            gets(str);
            for(j = 0; j < x; j++)
            {
                graph[i][j] = str[j];
                if(graph[i][j] == 'S')
                {
                    node[0].y = i;  //S结点编0号
                    node[0].x = j;
                }
                if(graph[i][j] == 'A')
                {
                    ncount++;
                    node[ncount].y = i;
                    node[ncount].x = j;
                }
            }
        }
        ncount++;
        for(i = 0; i < ncount; i++)
            bfs(i); //产生各个字母间最短路长，记录在map中
        printf("%d\n", prim(0));
    }
    return 0;
}