#include"stdio.h"
#include"string.h"
#include"queue"
using namespace std;
#define N 200          //N为100就wrong了
#define M 200
const int inf=10000;
int map[N][N];
char str[N][N];
int row,col;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
struct node
{
	int x,y,t;
	friend bool operator<(node a,node b)
	{
		return a.t>b.t;
	}
}f[M];
int judge(int x,int y)
{
	if(x>=0&&x<row&&y>=0&&y<col&&str[x][y]!='#')
		return 1;
	return 0;
}
void bfs(int index,int n)
{
	int i,di,dj,cnt=0;
	int mark[M][M];     //标记该点是否在队列
	priority_queue<node>q;
	node cur,next;
	cur.x=f[index].x;
	cur.y=f[index].y;
	cur.t=0;
	q.push(cur);
	memset(mark,0,sizeof(mark));
	mark[cur.x][cur.y]=1;
	while(!q.empty())
	{
		cur=q.top();
		q.pop();
		for(i=0;i<n;i++)
		{
			if(cur.x==f[i].x&&cur.y==f[i].y)
			{
				map[index][i]=map[i][index]=cur.t;
				cnt++;
				break;
			}
		}
		if(cnt==n)
			break;
		for(i=0;i<4;i++)
		{
			next.x=di=cur.x+dx[i];
			next.y=dj=cur.y+dy[i];
			next.t=cur.t+1;
			if(judge(di,dj)&&!mark[di][dj])
			{
				mark[di][dj]=1;
				q.push(next);
			}
		}
	}
}
int prim(int n)
{
	int i,index,min,sum=0;
	int dis[M],mark[M];
	for(i=0;i<n;i++)
		dis[i]=map[0][i];
	memset(mark,0,sizeof(mark));
	mark[0]=1;
	while(1)
	{
		index=-1;
		min=inf;
		for(i=0;i<n;i++)
			if(!mark[i]&&dis[i]<min)
			{
				min=dis[i];
				index=i;
			}
		if(index==-1)
			return sum;
		mark[index]=1;
		sum+=min;
		for(i=0;i<n;i++)
			if(!mark[i]&&dis[i]>map[index][i])
				dis[i]=map[index][i];
	}
	return 0;
}
int main()
{
	int T,i,j,n;
	char temp[200];
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&col,&row);
		gets(temp);
		for(i=0;i<row;i++)
			gets(str[i]);
		for(i=0,n=0;i<row;i++)
			for(j=0;j<col;j++)
			{
				if(str[i][j]=='S'||str[i][j]=='A')
				{
					f[n].x=i;
					f[n++].y=j;
				}
			}
		for(i=0;i<n;i++)
			bfs(i,n);           //把该点与所有点的距离都求出来
		printf("%d\n",prim(n));
	}
	return 0;
}