题目描述

我们来考虑一个由两名玩家 A 和 B 参与的游戏。该游戏由两个正整数 $X$ 和 $Y$ 决定。

游戏由若干局（set）组成，每一局又由若干回合（play）组成。在每一回合中，恰好有一名玩家（A 或 B）获胜。当某名玩家在该局中率先获得 $X$ 次胜利时，该局立即结束，该玩家成为该局的胜者。两名玩家不断进行局的比拼，直到其中一人率先获得 $Y$ 局的胜利。此时，游戏结束，该玩家成为整场游戏的胜者。

你刚刚观看了这场游戏，但没有注意到最终谁被宣布为胜者。你记得在游戏过程中总共进行了 $n$ 个回合，并且你知道每个回合的获胜者是谁，但你并不知道 $X$ 和 $Y$ 的具体数值。请根据已知信息，判断整场游戏的胜者究竟是 A 还是 B。如果无法确定胜者，也请给出相应的结论。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 20$），表示游戏中总共进行了 $n$ 个回合。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，仅由字符 $\texttt{A}$ 和 $\texttt{B}$ 组成。如果 $s_i = \texttt{A}$，表示第 $i$ 个回合由玩家 A 获胜；如果 $s_i = \texttt{B}$，表示第 $i$ 个回合由玩家 B 获胜。

保证给定的回合序列对于某些 $X$ 和 $Y$ 的取值下，至少存在一种合法的游戏过程。

输出格式

对于每个测试用例，输出一行：

• 如果玩家 A 一定是整场游戏的胜者，输出 $\texttt{A}$。
• 如果玩家 B 一定是整场游戏的胜者，输出 $\texttt{B}$。
• 如果无法确定整场游戏的胜者，输出 $\texttt{?}$。

说明/提示

在第一个测试用例中，游戏可能采用参数 $X = 3$，$Y = 1$。此时游戏只进行了一局，A 在前 $3$ 个回合中获胜，因此 A 获得该局胜利，成为整场游戏的胜者。游戏也可能采用参数 $X = 1$，$Y = 3$。可以证明不存在某种 $X$ 和 $Y$ 的取值使得 B 获胜。

在第二个测试用例中，B 赢得了所有回合。很容易证明，在这种情况下，B 一定是整场游戏的胜者。

在第四个测试用例中，游戏可能采用参数 $X = 3$，$Y = 3$：

• 第一局进行了 $3$ 个回合：AAA。A 获得该局胜利。
• 第二局进行了 $3$ 个回合：AAA。A 获得该局胜利。
• 第三局进行了 $5$ 个回合：AABBB。B 获得该局胜利。
• 第四局进行了 $5$ 个回合：AABBB。B 获得该局胜利。
• 第五局进行了 $4$ 个回合：BBAB。B 获得该局胜利。

最终，B 首先获得 $3$ 局胜利，因此 B 成为整场游戏的胜者。

由 ChatGPT 4.1 翻译

样例

7
5
ABBAA
3
BBB
7
BBAAABA
20
AAAAAAAABBBAABBBBBAB
1
A
13
AAAABABBABBAB
7
BBBAAAA

A
B
A
B
A
B
A