#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
#define INF 10000000

struct point
{
	int px,py;
	int d;
} points[102];

int x,y,num;//input y行x列 aliens'num
//****BFS*****
char map[52][52];//储存迷宫地图
int visit[52][52];
queue<point> q;//BFS
int flag[552];
int direct[4][2]  = {{1,0},{0,1},{-1,0},{0,-1}};
//*****Prim*****
int edges[102][102];//记录edges[i]记录i到其他所有点的距离
int values[102];//Prim中点权重记录

void input()
{
    num = 0;
	for(int i = 0;i < y;i++)
	{
		gets(map[i]);
		for(int j = 0;j < x;j++)
			if(map[i][j] == 'A' || map[i][j]=='S')
			{	
				points[num].px = i;
				points[num].py = j;
				points[num].d = 0;
				flag[i*10+j] = num;
				values[num] = INF;
				if(map[i][j] == 'S') values[num] = 0;
				num++;
		    }
	}
}

void BFS(int u)
{
	point t;int time = 0;
	q.push(points[u]);
	while(!q.empty())
	{
		point p = q.front();
		q.pop();
		//判断是否为A或者S
		if(map[p.px][p.py] == 'A' || map[p.px][p.py]=='S')
	    {
			edges[u][flag[p.px*10+p.py]] = p.d;
			time++;
	    }
		visit[p.px][p.py] = 1;
		//将合法的四个方向压入q
		for(int i = 0;i < 4;i++)
		{
			int xx = p.px + direct[i][0];
			int yy = p.py + direct[i][1];
			if(map[xx][yy] != '#' && !visit[xx][yy])
			{
				visit[xx][yy] = 1; //这句话导致了TLE
				t.px = xx;
				t.py = yy;
				t.d = p.d+1;
				q.push(t);
			}
		}
	}
}

void countEdges()
{
	for(int i = 0; i < num;i++)
	{
		memset(visit , 0 ,sizeof(visit));
	    BFS(i);
	}
}

int MST_Prim()
{
	int sum = 0;
	for(int k = 0;k < num;k++)
	{
		int index = -1;int min = INF;
		for(int i = 0;i < num;i++)
			if(values[i] >= 0 && min > values[i])
			{
				min = values[i];
				index = i;
			}
		values[index] = -1;
		sum += min;
		for(int i = 0;i < num;i++)
			if(values[i] >= 0 && edges[index][i] < values[i])
				values[i] = edges[index][i];
	}
	return sum;
}

int main()
{
	int T = 0;char c[51];
	cin >> T;
	while(T--)
	{
		cin >> x >> y;
		gets(c);
		input();
		countEdges();
		cout<<MST_Prim()<<endl;
	}
	return 0;
}