> #include<iostream>
> #include<queue>
> #define  INF 100000
> using namespace std;
> struct st {
> 	int i;
> 	int j;
> }stu[150],a,d;
> char str[100][100],ch;
> int n,m,length;
> int c[150][150];
> int step;
> queue<st> q;
> void dfs(st b){
> 	step = 0;
> 	int e[150][150],i,j;
> 	for(i = 0;i<n;i++)
> 		for(j = 0;j<m;j++)
> 			e[i][j] = 0;
> 	while (1) {
> 		int len = q.size();
> 		while(len>0){
> 			a = q.front();
> 			if(a.i == b.i&&a.j==b.j)
> 				return ;
> 			if(a.i-1>=0&&str[a.i-1][a.j]!='#'&&e[a.i-1][a.j]==0){
> 				d.i = a.i -1;
> 				d.j = a.j;
> 				q.push(d);
> 				e[d.i][d.j] = 1;
> 			}
> 			if(a.i+1<n&&str[a.i+1][a.j]!='#'&&e[a.i+1][a.j]==0){
> 				d.i = a.i+1;
> 				d.j = a.j;
> 				q.push(d);
> 				e[d.i][d.j] = 1;
> 			}
> 			if(a.j+1<m&&str[a.i][a.j+1]!='#'&&e[a.i][a.j+1]==0){
> 				d.i = a.i;
> 				d.j = a.j+1;
> 				q.push(d);
> 				e[d.i][d.j] = 1;
> 			}
> 			if(a.j-1>=0&&str[a.i][a.j-1]!='#'&&e[a.i][a.j-1]==0){
> 				d.i = a.i;
> 				d.j = a.j-1;
> 				q.push(d);
> 				e[d.i][d.j] = 1;
> 			}
> 			len--;
> 			q.pop();
> 
> 		}
> 		step++;
> 	}
>  }
> void prim(){
> 	int lowcost[150];
> 	int closet[150];
> 	bool s[150];
> 	s[0] = true;
> 	int i,j,k;
> 	for(i = 1;i<length;i++){
> 		lowcost[i] = c[0][i];
> 		closet[i] = 1;
> 		s[i] = false;
> 	}
> 
> 	for(i = 0;i<n;i++){
> 		int min = INF;
> 		j = 0;
> 		for(k = 1;k<length;k++)
> 			if(lowcost[k]<min&&(!s[k])){
> 				min = lowcost[k];
> 				j = k;
> 			}
> 		s[j] = true;
> 		for(k = 1;k<length;k++)
> 			if(c[j][k]<lowcost[k]&&(!s[k])){
> 				lowcost[k] = c[j][k];
> 				closet[k]=j;
> 			}
> 	}
> 	int sum = 0;
> 	for(i = 1;i<length;i++)
> 		sum+=lowcost[i];
> 	printf("%d\n",sum);
> 
> 
> }
> int main()
> {
> 	int t,i,j;
> //	freopen("in.txt","r",stdin);
> 	scanf("%d",&t);
> 	while (t--) {
> 		scanf("%d%d",&m,&n);
> 		length = 0;
> 		for(i = 0;i<n;i++){
> 			scanf("%c",&ch);
> 			for(j = 0;j<m;j++){
> 				scanf("%c",&str[i][j]);
> 				if(str[i][j]=='S'||str[i][j]=='A'){
> 					stu[length].i = i;
> 					stu[length].j = j;
> 					length++;
> 				}
> 			}
> 		}
> 		for(i = 0;i<length;i++){
> 			c[i][i] = 0;
> 			for(j = i+ 1;j<length;j++){
> 				q.push(stu[i]);
> 				dfs(stu[j]);
> 				c[i][j] = step;
> 				c[j][i] = step;
> 				step = 0;
> 			while (!q.empty()) 
> 				q.pop();
> 			}
> 		}
> 		prim();
> 	}
> 	return 0;
> }