题目描述

题目译自 BalticOI 2008 Day1「Game」

玩家 $\text{A}$ 和玩家 $\text{B}$，在一个 $n\times n$ 的正方形方格板上玩游戏。方格板上的方格要么是白的，要么是黑的。游戏只在白色区域上进行，黑色区域是禁区。初始时，每位玩家的起点上，会放置一个棋子。保证两人起点不同。
玩家交替移动，玩家 $\text{A}$ 先移动。每次移动，玩家会将他的棋子移动到相邻的白色方格中。如果玩家将棋子移动到对方现在的位置，玩家可以再移动一步，以越过对手。注意在这种情况下，第二步移动的方向可以与第一步移动的不同。
这个游戏的目标是玩家的棋子首先到达对方的起点，先到者为胜。即使玩家的最后一步包含两次移动，并且他只是越过了对手的起点（如果对手现在在起点），这个玩家也获得胜利。
给出方格板的布局和两个玩家的起点，判定哪个玩家有必胜策略（如果对手不管怎样移动，一个玩家能获得胜利，就称一个玩家有必胜策略）。

输入格式

标准输入的第一行包含一个正整数 $t$，表示测试数据的组数（$1\le t \le 10$）。在此之后为 $t$ 组测试数据。每一组测试数据格式如下：
在这组数据的第一行是一个正整数 $n$，表示方格的边长（$2\le n\le 300$），之后的每一行包含 $n$ 个字符（字符之间无空格）。每个字符是 .（一个白色方格），#（一个黑色方格），A（$\text{A}$ 的起点）和 B（$\text{B}$ 的起点）其中之一。

保证在两人的起点间存在一条白色方格的通路。

输出格式

对于每组数据，输出一行到标准输出，包含一个字符 A 或 B，表示有着必胜策略的玩家。

2
4
A...
.#..
....
...B
4
A...
....
..#.
...B

B
A

数据范围与提示

对于 $40\%$ 的数据， $n \le 40$。
对于 $60\%$ 的数据， $n \le 150$。
对于所有数据，$2\le n\le 300$。