本题至少得是紫题吧……反正思路很复杂，代码也难写，还要卡时、空常数。

拿出草稿纸手玩样例后，首先有如下结论：

1. 双方一定走最短路。

证明：如果有一方不走最短路，那么另一方走最短路就一定能赢。

2. 如果最短路的长度为奇数，则 A 必胜。

证明：如果 A、B 不碰面，则 A 必胜（显然）。如果 A、B 碰面，则一定是 A 从 B 头上跳过，A 反而走得更快了，B 没法翻盘。

3. 如果 A 有一种走法，使得无论 B 怎么走，A 都可以不碰上 B，则 A 必胜；否则 A 必败。

证明：如果 A 碰上 B，此时是 B 从 A 的头上跳过，B 可以实现翻盘。不然 B 永远无法翻盘。

有了上述结论，本题还是很困难。第三个结论比较难判。

先两次 bfs，求出 A、B 到达每个点的最短距离。下面只关心关键点，也就是在 A、B 最短路径上的点。同样也可以求出 A、B 可能在哪些点上相遇，这些点称作相遇点。

这样我们有思路：

枚举一个从 A 开始走 $i$ 步到达的关键点，看看其继续往下走，能到达的相遇点集合 $S_1$；

再枚举从 B 开始走 $i$ 步到达的关键点，其继续往下走，能到达的相遇点集合记为 $S_2$；

如果对于所有的 $S_2$ 都有 $S_1 \not \subset S_2$，则意味着从 A 开始走到达了这个点，就可以避开 B，A 就可以获胜，完美！

对于集合属于关系的判定，可以考虑 bitset，每个关键点能到达的相遇点用 bitset 存储。倒序循环 $i$，类似于动态规划来转移集合。

不知道为啥空间限制这么严。建议多使用动态数组 vector 以节省内存。

#include <bits/stdc++.h>
#define ll long long
#define rep(i, s, t) for(int i=s; i<=t; ++i)
#define debug(x) cerr<<#x<<":"<<x<<endl;
const int N=305;
using namespace std;

int n; char mp[N][N]; bool flag[N][N];
bitset<N> finals[N][N];
struct node {int i, j;} sa, sb;
int da[N][N], db[N][N], dis;
int dx[]={-1, 1, 0, 0}, dy[]={0, 0, -1, 1};
void bfs(node st, int d[N][N])
{
	memset(d, 0x3f, sizeof da);
	queue<node> q; q.push(st); d[st.i][st.j]=0;
	while(q.size())
	{
		auto [i,j]=q.front(); q.pop();
		rep(k, 0, 3)
		{
			int ni=i+dx[k], nj=j+dy[k];
			if(ni<1 || ni>n || nj<1 || nj>n) continue;
			if(mp[ni][nj]=='#') continue;
			if(d[i][j]+1<d[ni][nj])
				d[ni][nj]=d[i][j]+1, q.push({ni, nj});
		}
	}
}

void extend(int i, int j, int d[N][N])
{
	rep(k, 0, 3)
	{
		int ni=i+dx[k], nj=j+dy[k];
		if(ni<1 || ni>n || nj<1 || nj>n) continue;
		if(mp[ni][nj]=='#') continue;
		if(d[i][j]+1==d[ni][nj] && flag[ni][nj])
			finals[i][j]|=finals[ni][nj];
	}
}

void solve()
{	
	scanf("%d", &n);
	rep(i, 1, n) scanf("%s", &mp[i][1]);
	rep(i, 1, n) rep(j, 1, n)
	{
		finals[i][j].reset();
		flag[i][j]=0;		
		if(mp[i][j]=='A') sa={i, j};
		if(mp[i][j]=='B') sb={i, j};
	}
	bfs(sa, da), bfs(sb, db);	
	dis=da[sb.i][sb.j];
	if(dis&1) return puts("A"), void();
	rep(i, 1, n) rep(j, 1, n) if(da[i][j]+db[i][j]==dis) flag[i][j]=1;
	int k=0;
	rep(i, 1, n) rep(j, 1, n) if(da[i][j]*2==dis)
	{
		finals[i][j]=1<<k, k++;
	}
	vector<vector<node>> vec(dis+1);
	rep(i, 0, dis) vec[i].clear(); 
	rep(i, 1, n) rep(j, 1, n) if(flag[i][j])
		vec[da[i][j]].push_back({i, j});
	for(int k=dis/2-1; k>=0; k--)
	{
		for(auto [i,j]:vec[k]) extend(i, j, da);
		for(auto [i,j]:vec[dis-k]) extend(i, j, db);
		for(auto [i,j]:vec[k])
		{
			bool can_reach=0;
			for(auto [ii,jj]:vec[dis-k])
			{
				if((finals[i][j]&finals[ii][jj])==finals[i][j])
				{
					can_reach=1; break;
				}
			}
			if(!can_reach)
			{
				puts("A"); return;
			}
		}
	}
	puts("B");
}

int main()
{
#ifdef Jerrywang
	freopen("E:/OI/in.txt", "r", stdin);
#endif
	int T; scanf("%d", &T);
	while(T--) solve();
	
	return 0;
}