AT_agc078_c.AB vs. BA

You are given a string $S$ of length $N$ consisting of A and B. Abel and Bart play a game using $S$. Starting with Abel, they take turns performing the following operation.

• Abel chooses one substring AB of $S$ and deletes it.
• Bart chooses one substring BA of $S$ and deletes it.

The person who cannot perform the operation on their turn loses, and the other person wins. Find the winner when both players act optimally.

Solve $T$ test cases for each input.

给你一个长度为 $N$ 的字符串 $S$，仅由字符 A 和 B 组成。Abel 和 Bart 使用 $S$ 进行一场游戏。游戏从 Abel 开始，两人轮流执行以下操作：

• Abel 选择 $S$ 中的一个子串 AB 并将其删除；
• Bart 选择 $S$ 中的一个子串 BA 并将其删除。

无法在自己的回合执行操作的人输掉游戏，另一人获胜。当双方均以最优策略进行游戏时，请判断胜者。

对每组输入求解 $T$ 个测试用例。

The input is given from Standard Input in the following format:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format:

$N$
$S$

输入从标准输入中以如下格式给出：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例以如下格式给出：

$N$
$S$

Output $T$ lines. The $i$-th line should contain Abel if Abel wins the $i$-th test case, and Bart otherwise.

输出 $T$ 行。第 $i$ 行应包含 Abel（如果 Abel 赢得第 $i$ 个测试用例），否则包含 Bart。

Sample 1 Explanation:
In the first test case, if Abel deletes the left AB, then $S=$ AAB, and Bart cannot perform the operation, so Abel wins.

In the second test case, if Abel deletes AB, then $S=$ ABA. Next, if Bart deletes BA, then $S=$ A, and Abel cannot perform the operation, so Bart wins.

Constraints

• $1 \le T \le 2 \times 10^5$
• $1 \le N \le 2 \times 10^5$
• $S$ is a string of length $N$ consisting of A and B.
• The sum of $N$ over the $T$ test cases is at most $2 \times 10^5$.
• All input values are integers.

样例 1 解释：
在第一个测试用例中，若 Abel 删除左侧的 AB，则 $S=$ AAB，此时 Bart 无法执行操作，因此 Abel 获胜。

在第二个测试用例中，若 Abel 删除 AB，则 $S=$ ABA。接下来，若 Bart 删除 BA，则 $S=$ A，此时 Abel 无法执行操作，因此 Bart 获胜。

约束条件

• $1 \le T \le 2 \times 10^5$
• $1 \le N \le 2 \times 10^5$
• $S$ 是一个长度为 $N$ 的字符串，仅由字符 A 和 B 组成。
• 所有 $T$ 个测试用例的 $N$ 值之和不超过 $2 \times 10^5$。
• 所有输入值均为整数。