两个玩家 $A$ 和 $B$ 在一个大小为 $n \times n$ 的网格棋盘上玩游戏。棋盘上的方格要么是白色的，要么是黑色的。游戏仅在白色方格上进行——黑色方格不参与游戏。每个玩家拥有一枚棋子，初始时放置在该玩家的起点——棋盘上的某个白色方格。$A$ 的起点与 $B$ 的起点不同。

在每一步移动中，玩家可以将自己的棋子移动到相邻的白色方格之一（上、下、左或右）。如果玩家将棋子移动到对手棋子当前所在的方格，他将获得一次额外的移动机会（通过这种方式，他可以跳过对手）。请注意，在这种情况下，第二次移动的方向可以与第一次移动的方向不同。

玩家 $A$ 先手，然后双方轮流移动。游戏的目标是到达对手的起点。最先让自己的棋子到达对手起点的玩家获胜。我们希望确定哪位玩家拥有必胜策略（如果一个玩家无论对手如何移动都能获胜，则称其拥有必胜策略）。

图 1。如果 A 在前三步中向右移动，B 将在前三步中向上移动。因此，在第三步时，玩家 B 将到达 A 棋子所在的方格，并被允许再次移动。正因如此，B 将率先到达 A 的起点并赢得游戏。

图 2。A 可以先向右移动一步，再向下移动一步。然后，根据 B 的前两步移动，他将向下或向右移动并避开 B。这样 A 将率先到达 B 的起点，从而赢得游戏。事实上，我们证明了 A 拥有必胜策略。

任务

编写一个程序：

• 从标准输入读取网格的布局和两位玩家的起点，
• 找出拥有必胜策略的玩家，
• 将结果写入标准输出。

输入格式

第一行包含一个整数 $t$，表示测试数据的组数（$1 \le t \le 10$）。接下来是 $t$ 组测试数据的描述。每组测试数据的描述如下：

第一行包含一个整数 $n$（$2 \le n \le 300$），表示网格的边长。

接下来的 $n$ 行包含网格的描述。每行包含 $n$ 个字符（字符之间没有空格）。每个字符为以下之一：

• .（白色方格）
• #（黑色方格）
• A（$A$ 的起点）
• B（$B$ 的起点）

你可以假设 $A$ 和 $B$ 的起点之间存在一条由白色方格组成的路径。

输出格式

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

数据范围

• $1 \le t \le 10$
• $2 \le n \le 300$
• 在占总分 $60\%$ 的测试数据中，$n \le 150$。
• 在占总分 $40\%$ 的测试数据中，$n \le 40$。

样例

输入样例 1

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

输出样例 1

B
A