CF1894A.Secret Sport

Let's consider a game in which two players, A and B, participate. This game is characterized by two positive integers, $X$ and $Y$.

The game consists of sets, and each set consists of plays. In each play, exactly one of the players, either A or B, wins. A set ends exactly when one of the players reaches $X$ wins in the plays of that set. This player is declared the winner of the set. The players play sets until one of them reaches $Y$ wins in the sets. After that, the game ends, and this player is declared the winner of the entire game.

You have just watched a game but didn't notice who was declared the winner. You remember that during the game, $n$ plays were played, and you know which player won each play. However, you do not know the values of $X$ and $Y$. Based on the available information, determine who won the entire game — A or B. If there is not enough information to determine the winner, you should also report it.

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

游戏由若干“局”（sets）组成，而每一局又由若干“回合”（plays）组成。在每个回合中，恰好有一名玩家（A 或 B）获胜。当某一名玩家在该局的回合中赢得 $X$ 次时，该局立即结束；这名玩家即被判定为该局的胜者。玩家们持续进行局的比拼，直到其中一名玩家累计赢得 $Y$ 局为止；此时整个游戏结束，该玩家即被判定为整场游戏的胜者。

你刚刚观看了一场游戏，但未留意最终谁被宣布为整场游戏的胜者。你只记得整场游戏中共进行了 $n$ 个回合，并且你知道每个回合的胜者是 A 还是 B。然而，你并不知道参数 $X$ 和 $Y$ 的具体取值。基于这些已知信息，请判断整场游戏的胜者是 A 还是 B；若根据现有信息无法唯一确定胜者，则也需如实报告。

Each test contains multiple test cases. The first line contains a single integer $t$ $(1 \leq t \leq 10^4)$ - the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ $(1 \leq n \leq 20)$ - the number of plays played during the game.

The second line of each test case contains a string $s$ of length $n$, consisting of characters $\texttt{A}$ and $\texttt{B}$. If $s_i = \texttt{A}$, it means that player A won the $i$-th play. If $s_i = \texttt{B}$, it means that player B won the $i$-th play.

It is guaranteed that the given sequence of plays corresponds to at least one valid game scenario, for some values of $X$ and $Y$.

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

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

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

保证所给的回合序列至少对应一个合法的游戏情形（即存在某些 $X$ 和 $Y$ 的取值使得该序列合法）。

For each test case, output:

• $\texttt{A}$ — if player A is guaranteed to be the winner of the game.
• $\texttt{B}$ — if player B is guaranteed to be the winner of the game.
• $\texttt{?}$ — if it is impossible to determine the winner of the game.

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

• $\texttt{A}$ — 若玩家 A 必然赢得游戏；
• $\texttt{B}$ — 若玩家 B 必然赢得游戏；
• $\texttt{?}$ — 若无法确定游戏的获胜者。

In the first test case, the game could have been played with parameters $X = 3$, $Y = 1$. The game consisted of $1$ set, in which player A won, as they won the first $3$ plays. In this scenario, player A is the winner. The game could also have been played with parameters $X = 1$, $Y = 3$. It can be shown that there are no such $X$ and $Y$ values for which player B would be the winner.

In the second test case, player B won all the plays. It can be easily shown that in this case, player B is guaranteed to be the winner of the game.

In the fourth test case, the game could have been played with parameters $X = 3$, $Y = 3$:

• In the first set, $3$ plays were played: AAA. Player A is declared the winner of the set.
• In the second set, $3$ plays were played: AAA. Player A is declared the winner of the set.
• In the third set, $5$ plays were played: AABBB. Player B is declared the winner of the set.
• In the fourth set, $5$ plays were played: AABBB. Player B is declared the winner of the set.
• In the fifth set, $4$ plays were played: BBAB. Player B is declared the winner of the set.

In total, player B was the first player to win $3$ sets. They are declared the winner of the game.

在第一个测试用例中，游戏可能使用参数 $X = 3$、$Y = 1$ 进行。整场游戏包含 $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$ 局的选手，因此被宣布为整场游戏的获胜者。