#include<iostream>
#include <sstream>
#include<string>
#include<cstdlib>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<stack>
#include<queue>
#include<fstream>
#include<cassert>
#include<map>
#include<set>
#include<vector>
#include<cstring>
#include<algorithm>
#include"limits.h"
using namespace std;
struct Node
{
    int x,y;
    int cost;
    bool mark;
    Node(int a=0,int b=0):x(a),y(b),cost(INT_MAX),mark(0){
    }
};
struct Map
{
    char map[60][60];
    int row,col;
    std::vector<Node> v;
    int Dic[60][60];
    int execnt;
    void buildMap();
    void showMap();
    void DfsStart();
    void showDic();
    bool outOfMap(int x,int y);
    void DfsNode(int x,int y);
    int minimumLenth();
};
int Map::minimumLenth()
{
    v[0].mark=1;
    int curNode=0;
    int sum=0;
    for (int i = 0; i < v.size()-1; ++i)
    {
        // sum+=v[curNode].cost;
        DfsNode(v[curNode].x, v[curNode].y);
        int minV=INT_MAX;
        for (int j = 0; j < v.size(); ++j)
        {
            if (!v[j].mark&&v[j].cost<minV)
            {
                minV=v[j].cost;
                curNode=j;
            }
        }
        // cout<<"select Node: "<<curNode<<endl;
        // cout<<"\tminV add: "<<minV<<endl;
        sum+=minV;
        // cout<<"showDic:\n";
        // showDic();
        v[curNode].mark=1;
    }
    // showMap();
    return sum;
}
inline bool Map::outOfMap(int x,int y)
{
    return x<0||x>=row||y<0||y>=col;
}
void Map::showDic()
{
    int k=0;
    for (std::vector<Node>::iterator i = v.begin(); i != v.end(); ++i)
    {
        cout<<k++<<": "<<i->x<<" "<<i->y<<" "<<i->cost<<endl;
    }
}
struct searchNode
{
    int x,y,depth;
    searchNode(int a,int b,int d=0):x(a),y(b),depth(d){
    }
};
void Map::DfsNode(int x,int y)
{
    int depthLimit=100;
    int ndpos=Dic[x][y];
    int mark[60][60]={0};
    queue<searchNode> q;
    int cnt=0;
    q.push(searchNode(x,y));
    while(q.size())
    {
        searchNode current=q.front();
        q.pop();
        int x=current.x,y=current.y,d=current.depth;
        // cout<<"queue Node:"<<x<<"\t"<<y<<"\t"<<d<<endl;
        if (mark[x][y])
        {
            continue;
        }
        cnt++;
        mark[x][y]=1;
        if (d>depthLimit)
        {
            break;
        }
        ndpos=Dic[x][y];
        if (map[x][y]=='A'&&!v[ndpos].mark)
        {
            depthLimit=d+45;
            // cout<<"ndpos="<<ndpos<<endl;
            // cout<<"found "<<x<<","<<y<<" currentCost:"<<v[ndpos].cost;
            // cout<<" depth "<<d<<endl;
            if (v[ndpos].cost>d)
            {
                // cout<<"update "<<x<<","<<y<<" to "<<d<<endl;
                v[ndpos].cost=d;
            }
        }
        if (!outOfMap(x-1, y)&&map[x-1][y]!='#')
        {
            q.push(searchNode(x-1,y,d+1));
        }
        if (!outOfMap(x+1, y)&&map[x+1][y]!='#')
        {
            q.push(searchNode(x+1,y,d+1));
        }
        if (!outOfMap(x, y-1)&&map[x][y-1]!='#')
        {
            q.push(searchNode(x,y-1,d+1));
        }
        if (!outOfMap(x, y+1)&&map[x][y+1]!='#')
        {
            q.push(searchNode(x,y+1,d+1));
        }
    }
    execnt+=cnt;
    // cout<<"time of execution= "<<cnt<<endl;
    // cout<<"searchDepth= "<<depthLimit<<endl;

}
void Map::DfsStart()
{
    int mark[60][60]={0};
    queue<searchNode> q;
    q.push(searchNode(v[0].x,v[0].y));
    while(q.size())
    {
        searchNode current=q.front();
        q.pop();
        int x=current.x,y=current.y,d=current.depth;
        if (mark[x][y])
        {
            continue;
        }
        execnt++;
        mark[x][y]=d;
        // cout<<"current: " <<x<<" "<<y<<endl;
        if (map[x][y]=='A')
        {
            v[Dic[x][y]].cost=d;
        }
        if (!outOfMap(x-1, y)&&map[x-1][y]!='#')
        {
            q.push(searchNode(x-1,y,d+1));
        }
        if (!outOfMap(x+1, y)&&map[x+1][y]!='#')
        {
            q.push(searchNode(x+1,y,d+1));
        }
        if (!outOfMap(x, y-1)&&map[x][y-1]!='#')
        {
            q.push(searchNode(x,y-1,d+1));
        }
        if (!outOfMap(x, y+1)&&map[x][y+1]!='#')
        {
            q.push(searchNode(x,y+1,d+1));
        }
    }
    // showDic();
}
void Map::showMap()
{
    for (int i = 0; i < row; ++i)
    {
        // cout<<i<<"=";
        for (int j = 0; j < col; ++j)
        {
            if (map[i][j]=='A'&&v[Dic[i][j]].cost!=INT_MAX)
            {
                cout<<v[Dic[i][j]].cost;
            }
            else
                cout<<map[i][j];
        }
        cout<<"\n";
    }
    cout<<endl;
}
void Map::buildMap()
{
    execnt=0;
    cin>>col>>row;
    memset(map, ' ', sizeof(map));
    memset(Dic, INT_MAX, sizeof(Dic));
    v.push_back(Node());
    v[0].mark=1;
    while(getchar() != '\n');
    for (int i = 0; i < row; ++i)
    {
        string tmp;
        getline(cin,tmp);
        for (int j = 0; j < tmp.size(); ++j)
        {
            map[i][j]=tmp[j];
            if (map[i][j]=='A')
            {
                // cout<<"push="<<i<<" "<<j<<endl;
                v.push_back(Node(i,j));
                Dic[i][j]=v.size()-1;
                continue;
            }
            if (map[i][j]=='S')
            {
                v[0].x=i;
                v[0].y=j;
                v[0].cost=0;
            }
        }
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    std::ios::sync_with_stdio(0);
    freopen("/Users/steven/Desktop/tmp.txt","r",stdin);
    clock_t a=clock();
    #endif
    int n;
    cin>>n;
    while(n--)
    {
        Map g;
        g.buildMap();
        // g.showMap();
        g.DfsStart();
        int s=g.minimumLenth();
        cout<<s<<endl;
        // cout<<"cnt= "<<g.execnt/(double)(g.col*g.row)<<endl;
    }
    #ifndef ONLINE_JUDGE
    clock_t b=clock();
    cout<<"running time:"<<(b-a)/(double)CLOCKS_PER_SEC<<endl;
    #endif
}