#include <stdio.h>
#include <string.h>
#define maxint 1000000000
typedef struct node
{
	int x;
	int y;
}P;
typedef struct N
{
	int x;
	int y;
	int step;
}Node;
int n,m;
int used[55][55];
char ch[55][55];
int d[5][3]={{1,0},{0,1},{-1,0},{0,-1}};
Node map[60000];
P point[60000];
int dis(P a,P b)
{
	memset(used,0,sizeof(used));
	int i,rear,front,flag,sum;
	int dx,dy;
	rear=-1;
	front=0;
	flag=1;
	map[0].x=a.x;
	map[0].y=a.y;
	map[0].step=0;
	if(a.x == b.x && a.y == b.y) return 0;
	while(front > rear && flag)
	{
		rear++;
		for(i=0;i<4;i++)
		{
			dx=map[rear].x+d[i][0];
			dy=map[rear].y+d[i][1];
			if(dx>=0 && dx<n && dy>=0 && dy<m && !used[dx][dy] && ch[dx][dy]!='#')
			{
				if(dx == b.x && dy== b.y)
				{
					flag=0;
					break;
				}
				front++;
				used[dx][dy]=1;
				map[front].x=dx;
				map[front].y=dy;
				map[front].step = map[rear].step+1;
			}
		}
	}
	sum=map[rear].step+1;
	return sum;
}
int main()
{
	int T,i,j,k,temp,s,sum;
	int c[60][60],lowcost[200],num[200];
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&m,&n);
		memset(ch,'\0',sizeof(ch));
		s=1;
		sum=0;
		getchar();
		for(i=0;i<n;i++) 
		{
			gets(ch[i]);
		}
		for(i=0;i<n;i++)
		{
			for(j=0;j<m;j++)
			{
				if(ch[i][j] == 'S' || ch[i][j] == 'A')
				{
					point[s].x = i;
					point[s].y = j;
					s++;
				}
			}
		}
		s--;
		for(i=1;i<=s;i++)
		{
			for(j=1;j<=s;j++)
			{
				c[i][j] = dis(point[i],point[j]);
				c[j][i] = dis(point[i],point[j]);
			}
		}
		memset(num,0,sizeof(num));
		num[1]=1;
		for(i=2;i<=s;i++)
		{
			lowcost[i] = c[1][i];
		}
		for(i=1;i<s;i++)
		{
			j=1;
			temp=maxint;
			for(k=2;k<=s;k++)
			{
				if(lowcost[k] < temp && !num[k])
				{
					temp = lowcost[k];
					j=k;
				}
			}
			num[j]=1;
			sum+=lowcost[j];
			for(k=2;k<=s;k++)
			{
				if(c[j][k] < lowcost[k] && !num[k])
				{
					lowcost[k] = c[j][k];
				}
			}
		}
		printf("%d\n",sum);
	}
	return 0;
}