Description

Player $\text{A}$ and player $\text{B}$ play a game on an $n \times n$ square grid. Each cell on the board is either white or black. The game is played only on the white cells; black cells are forbidden. Initially, each player has one piece placed at their own starting cell. It is guaranteed that the two starting cells are different.

The players move alternately, with player $\text{A}$ moving first. In each move, a player moves their piece to an adjacent white cell. If a player moves their piece onto the cell currently occupied by the opponent, the player may move one more step to jump over the opponent. Note that in this case, the direction of the second step may be different from the first step.

The goal of the game is to be the first player whose piece reaches the opponent’s starting cell. Even if the player’s last move consists of two steps and they only jump over the opponent’s starting cell (if the opponent is currently on that starting cell), the player still wins.

Given the board layout and the two players’ starting positions, determine which player has a winning strategy (a player has a winning strategy if they can win no matter how the opponent moves).

Input Format

The first line of standard input contains a positive integer $t$ ($1 \le t \le 10$), the number of test cases. Then follow $t$ test cases. Each test case is given as follows:

The first line of a test case contains a positive integer $n$ ($2 \le n \le 300$), the side length of the grid. Each of the next $n$ lines contains $n$ characters (with no spaces). Each character is one of . (a white cell), # (a black cell), A (the starting cell of $\text{A}$), and B (the starting cell of $\text{B}$).

It is guaranteed that there exists a path of white cells between the two starting cells.

Output Format

For each test case, output one line to standard output containing one character, A or B, indicating the player who has a winning strategy.

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

B
A

Hint

Sample Explanation

For the first test case:

If $\text{A}$ moves to the right edge of the grid within the first three moves, then $\text{B}$ will move upward within the first three moves. Therefore, on the third move, player $\text{B}$ will reach the cell where $\text{A}$ is and gain an extra move. Thus, $\text{B}$ will reach $\text{A}$’s starting cell first and win the game.

For the second test case:

$\text{A}$ can first move one step to the right and then one step down. After that, $\text{A}$ can decide whether to move down or right based on $\text{B}$’s first two moves, so as to avoid $\text{B}$. In this way, $\text{A}$ will reach $\text{B}$’s starting cell first and win the game. In fact, we have already proven that $\text{A}$ has a winning strategy.

Constraints

For $40\%$ of the testdata, $n \le 40$.

For $60\%$ of the testdata, $n \le 150$.

For all testdata, $2 \le n \le 300$.

Translated by ChatGPT 5