#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 50+5;
const int maxnVex = 100+5;
char map[maxn][maxn];
int sign[maxn][maxn];
int sign2[maxn][maxn];
int N,row,col; 	//行，列
int count1;	//s和A的总数量


typedef struct{
	int y,x;
	int num;
}Point;

struct Edg{
	int index;
	int lowCost;
}closeEdg[maxnVex];

queue<Point> Q;
Point vex[maxnVex];
int edg[maxnVex][maxnVex];


int dir[][2] = {{-1,0},{0,1},{1,0},{0,-1}};


void BFS(Point source){
	memset(sign,-1,sizeof(sign));
	int index = source.num;
	Q.push(source);
	sign[source.y][source.x] = 1;

	while(!Q.empty()){

			Point p = Q.front();
			Q.pop();
			char c = map[p.y][p.x];

			if(c=='#')	continue;	
			if(c=='S'||c=='A')	edg[index][p.num] = sign[p.y][p.x]-1;
			
			for(int i=0;i<4;i++){
				Point p1;
				p1.y = p.y+dir[i][0];
				p1.x = p.x+dir[i][1];
				if(map[p1.y][p1.x]=='S'||map[p1.y][p1.x]=='A')
					p1.num = sign2[p1.y][p1.x];


				
				if(sign[p1.y][p1.x]>0)	continue;

				if(p1.x<0||p1.y<0||p1.x>col||p1.y>row||map[p1.y][p1.x]=='#')	continue;

				sign[p1.y][p1.x] = sign[p.y][p.x]+1;
				Q.push(p1);
			}
	}

}


int min(){
	int k = 0;
	for(int i=0;i<count1;i++){
		if(closeEdg[i].lowCost==0)	continue;
		if(k==0)	k=i;
		if(closeEdg[k].lowCost>closeEdg[i].lowCost)	k = i;
	}
	return k;
}




int main(){

	int len = 0;
	cin>>N;
	while(N--){
		count1 = 0;
		cin>>col>>row;	//row行，col列
		gets(map[0]);
		for(int i=0;i<row;i++){
			gets(map[i]);
			for(int j=0;j<col;j++){
				if(map[i][j]=='S'||map[i][j]=='A'){
					vex[count1].x = j;
					vex[count1].y = i;
					vex[count1].num = count1;
					sign2[i][j] = count1;
					count1++;
				}

			}


		}



		for(int i=0;i<count1;i++){
			BFS(vex[i]);
		}

		

		closeEdg[0].index = 0;
		closeEdg[0].lowCost = 0;
		for(int i=1;i<count1;i++){
			closeEdg[i].index = 0;
			closeEdg[i].lowCost = edg[0][i];
		}

		for(int i=0;i<count1;i++){
			int k = min();
			len += closeEdg[k].lowCost;
			closeEdg[k].lowCost = 0;

			for(int j=0;j<count1;j++){
				if(edg[j][k]<closeEdg[j].lowCost){
					closeEdg[j].index = k;
					closeEdg[j].lowCost = edg[j][k];
				}
			}
		}
		
	cout<<len<<endl;
	len = 0;
	}
	return 0;
}