# Secret Sport Solution Codeforces

time limit per test

3 seconds

memory limit per test

512 megabytes

input

standard input

output

standard 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 playexactly one of the players, either A or B, wins. A set ends 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 (1t104)(1≤�≤104) – the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer n (1n20)(1≤�≤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 AA and BB. If si=A��=A, it means that player A won the i-th play. If si=B��=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:

• AA — if player A is guaranteed to be the winner of the game.
• BB — if player B is guaranteed to be the winner of the game.
• ?? — if it is impossible to determine the winner of the game.
Example
input

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

Copy
A
B
A
B
A
B
A

Note

In the first test case, the game could have been played with parameters X=3�=3Y=1�=1. The game consisted of 11 set, in which player A won, as they won the first 33 plays. In this scenario, player A is the winner. The game could also have been played with parameters X=1�=1Y=3�=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�=3Y=3�=3:

• In the first set, 33 plays were played: AAA. Player A is declared the winner of the set.
• In the second set, 33 plays were played: AAA. Player A is declared the winner of the set.
• In the third set, 55 plays were played: AABBB. Player B is declared the winner of the set.
• In the fourth set, 55 plays were played: AABBB. Player B is declared the winner of the set.
• In the fifth set, 44 plays were played: BBAB. Player B is declared the winner of the set.

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