310820: CF1894A. Secret Sport

A. Secret Sporttime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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.

ExampleInput

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

Output

A
B
A
B
A
B
A

Note

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.

题目大意：
这是一个两人游戏，玩家A和B参与。游戏由两个正整数X和Y定义。游戏由“局”组成，每局由多个“回合”组成。每个回合中，A或B中的一个玩家获胜。当一个玩家在一个局的回合中达到X次胜利时，这个局结束，这个玩家被宣布为这个局的赢家。玩家们一直玩局，直到其中一个玩家在局中达到Y次胜利。游戏结束，这个玩家被宣布为整个游戏的赢家。

你观看了整个游戏，但没注意谁赢了。你记得在整个游戏期间进行了n个回合，你知道每个回合哪个玩家赢了。然而，你不知道X和Y的值。根据现有信息，判断谁赢得了整个游戏——A还是B。如果信息不足以判断赢家，也应该报告。

输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含一个整数n（1≤n≤20）——游戏中进行的回合数。
每个测试用例的第二行包含一个长度为n的字符串s，由字符'A'和'B'组成。如果s_i='A'，这意味着玩家A赢得了第i个回合。如果s_i='B'，这意味着玩家B赢得了第i个回合。
保证给定的回合序列对应至少一个有效的游戏场景，对于某些X和Y的值。

输出数据格式：
对于每个测试用例，输出：
- A —— 如果玩家A肯定赢得游戏。
- B —— 如果玩家B肯定赢得游戏。
- ? —— 如果无法判断游戏的赢家。

示例：
输入：
7
5
ABBAA
3
BBB
7
BBAAABA
20
AAAAAAAABBBAABBBBBAB
1
A
13
AAAABABBABBAB
7
BBBAAAA

输出：
A
B
A
B
A
B
A

注意：
在第一个测试用例中，游戏可能以参数X=3，Y=1进行。游戏由1个局组成，其中玩家A赢得了前3个回合。在这种情况下，玩家A是赢家。游戏也可能以参数X=1，Y=3进行。可以证明，没有这样的X和Y值，使得玩家B成为赢家。
在第二个测试用例中，玩家B赢得了所有回合。可以很容易地证明，在这种情况下，玩家B肯定赢得整个游戏。
在第四个测试用例中，游戏可能以参数X=3，Y=3进行。在这种情况下，玩家B是赢家，因为他们是第一个赢得3个局的玩家。题目大意： 这是一个两人游戏，玩家A和B参与。游戏由两个正整数X和Y定义。游戏由“局”组成，每局由多个“回合”组成。每个回合中，A或B中的一个玩家获胜。当一个玩家在一个局的回合中达到X次胜利时，这个局结束，这个玩家被宣布为这个局的赢家。玩家们一直玩局，直到其中一个玩家在局中达到Y次胜利。游戏结束，这个玩家被宣布为整个游戏的赢家。 你观看了整个游戏，但没注意谁赢了。你记得在整个游戏期间进行了n个回合，你知道每个回合哪个玩家赢了。然而，你不知道X和Y的值。根据现有信息，判断谁赢得了整个游戏——A还是B。如果信息不足以判断赢家，也应该报告。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤20）——游戏中进行的回合数。 每个测试用例的第二行包含一个长度为n的字符串s，由字符'A'和'B'组成。如果s_i='A'，这意味着玩家A赢得了第i个回合。如果s_i='B'，这意味着玩家B赢得了第i个回合。 保证给定的回合序列对应至少一个有效的游戏场景，对于某些X和Y的值。 输出数据格式： 对于每个测试用例，输出： - A —— 如果玩家A肯定赢得游戏。 - B —— 如果玩家B肯定赢得游戏。 - ? —— 如果无法判断游戏的赢家。 示例： 输入： 7 5 ABBAA 3 BBB 7 BBAAABA 20 AAAAAAAABBBAABBBBBAB 1 A 13 AAAABABBABBAB 7 BBBAAAA 输出： A B A B A B A 注意： 在第一个测试用例中，游戏可能以参数X=3，Y=1进行。游戏由1个局组成，其中玩家A赢得了前3个回合。在这种情况下，玩家A是赢家。游戏也可能以参数X=1，Y=3进行。可以证明，没有这样的X和Y值，使得玩家B成为赢家。 在第二个测试用例中，玩家B赢得了所有回合。可以很容易地证明，在这种情况下，玩家B肯定赢得整个游戏。 在第四个测试用例中，游戏可能以参数X=3，Y=3进行。在这种情况下，玩家B是赢家，因为他们是第一个赢得3个局的玩家。