//自己感觉代码写的很乱，差点就看不懂了，还好过了。一开始不只咋的RE，后面对全部的数组加大了十倍，然后就过了
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
using namespace std;

struct Position  //广搜用的
{
	int x,y;

	int step;
}pos[1005];
int dist[501][501];
int map[501][501];
int t;
int x,y;
int visited[501][501];
int k = 0;
int direct[4][2]  = {{1,0},{0,1},{-1,0},{0,-1}};

void input()
{
	cin>>x>>y;
	char c  = getchar();
	while(c != '\n')
	{
		c = getchar();
	}
    char str[505];
	k = 0;
	for(int i = 1;i <= y;i++)
	{
		gets(str);
		int len = strlen(str);
		for(int j = 0;j < len;j++)
		{
			if(str[j] == '#')
			{
				map[i][j+1] = 1;
			}
			else if(str[j] == 'A' || str[j] == 'S')
			{
				pos[k].x = j+1;
				pos[k].y = i;
				pos[k].step = 0;
				k++;
			}
		}
	}
	/*
	for(int kk = 0;kk < k;kk++)
		cout<<"("<<pos[kk].y <<","<<pos[kk].x <<")  ";
	cout<<endl;
	*/
}
bool isok(int xx,int yy)    //判断往四个方向走是否越界
{
	if(xx >= 1 && xx <= x && yy >= 1 && yy <= y)
		return true;
	return false;
}
void computer(int mm)
{
	queue<Position> que;
	Position s,t;
	que.push(pos[mm]);
	int num = 0;
	visited[pos[mm].y][pos[mm].x] = 1;
	while(!que.empty())
	{
		s = que.front();
		que.pop();
		for(int j = 0;j < k && j != mm;j++)
		{
			if(s.x == pos[j].x && s.y == pos[j].y)
			{
				dist[mm+1][j+1] = s.step;
				dist[j+1][mm+1] = s.step;
				num++;
				break;
			}
		}
		if(num == k)
			break;
		for(int i = 0;i < 4;i++)
		{
			int xx = s.x + direct[i][0];
			int yy = s.y + direct[i][1];
			if(isok(xx,yy) && !map[yy][xx] && !visited[yy][xx])
			{
				visited[yy][xx] = 1;
				t.x = xx;
				t.y = yy;
				t.step = s.step + 1;
				que.push(t);
			}
		}
	}
	
}
void distance()   
{
	for(int i = 0;i < k;i++) //每次从“S”或“A”点出发，找出从当前点到其他“A”和“S”的距离，
	{                          //用广搜，本可以剪枝的
		memset(visited,0,sizeof(visited));
		computer(i);
	}
	/*
	for(int j = 1;j <= k;j++)
	{
		for(int kk = 1;kk <= k;kk++)
		{
			cout<<dist[j][kk]<<"   ";
		}
		cout<<endl;
	}
	cout<<endl;
	*/
}
void prim() //套用公式，没啥好说的，主要是距离数组的建立
{
	int visited_prim[105] = {0};
	int lowcost[105];
	int mincost = 0;

	int i,j;
	for(i = 2;i <= k;i++)
	{
		lowcost[i] = dist[1][i];
	}
	visited_prim[1] = 1;
	for(i = 1;i < k;i++)
	{
		int mmax = 2500;
		int node ;
		for(j = 2;j <= k;j++)
		{
			if(!visited_prim[j] && mmax > lowcost[j])
			{
				mmax = lowcost[j];
				node = j;
			}
		}
		visited_prim[node] = 1;
		mincost += mmax;
		for(j = 2;j <= k;j++)
		{
			if(!visited_prim[j] && lowcost[j] > dist[node][j])
			{
				lowcost[j] = dist[node][j];
			}
		}
	}
	cout<<mincost<<endl;
	return ;
}
int main()
{
	cin>>t;
	while(t--)
	{
	//	memset(pos,0,sizeof(pos));
		memset(map,0,sizeof(map));
		input();
		memset(dist,0,sizeof(dist));
		distance();
		prim();
	}
	system("pause");
	return 0;
}