A. Секретный спорт
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим игру, в которую играют два человека: A и B. Эта игра характеризуется двумя целыми положительными числами: $$$X$$$ и $$$Y$$$.

Игра состоит из сетов, каждый сет состоит из розыгрышей. В каждом розыгрыше побеждает ровно один из игроков — либо A, либо B. Сет заканчивается ровно тогда, когда один из игроков набирает $$$X$$$ побед в розыгрышах в течении этого сета. Этот игрок объявляется победителем сета. Игроки разыгрывают сеты до тех пор, пока один из них не наберёт $$$Y$$$ побед в сетах. После этого игра заканчивается, и этот игрок объявляется победителем всей игры.

Вы только что посмотрели игру, но не заметили, кого объявили победителем. Вы запомнили, что в течение игры было сыграно $$$n$$$ розыгрышей, а также кто из игроков победил в каждом из розыгрышей. Однако, вам неизвестны значения $$$X$$$ и $$$Y$$$. По имеющейся информации определите, кто из игроков победил во всей игре — A или B. Если информации недостаточно, чтобы определить победителя, вы также должны сообщить об этом.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ $$$(1 \leq n \leq 20)$$$ — количество сыгранных розыгрышей в течение игры.

Вторая строка каждого набора входных данных содержит последовательность $$$s$$$ длины $$$n$$$, состоящую из символов $$$\texttt{A}$$$ и $$$\texttt{B}$$$. Если $$$s_i = \texttt{A}$$$, это означает, что в $$$i$$$-м розыгрыше победил игрок A. Если $$$s_i = \texttt{B}$$$, это означает, что в $$$i$$$-м розыгрыше победил игрок B.

Гарантируется, что заданная последовательность розыгрышей соответствует хотя бы одному корректному сценарию игры при некоторых параметрах $$$X$$$ и $$$Y$$$.

Выходные данные

Для каждого набора входных данных в отдельной строке выведите:

  • $$$\texttt{A}$$$ — если победителем игры гарантированно является игрок A.
  • $$$\texttt{B}$$$ — если победителем игры гарантированно является игрок B.
  • $$$\texttt{?}$$$ — если невозможно однозначно определить победителя игры.
Пример
Входные данные
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$$$:

  • В первом сете было сыграно $$$3$$$ розыгрыша: AAA. Победителем сета считается игрок A.
  • Во втором сете было сыграно $$$3$$$ розыгрыша: AAA. Победителем сета считается игрок A.
  • В третьем сете было сыграно $$$5$$$ розыгрышей: AABBB. Победителем сета считается игрок B.
  • В четвёртом сете было сыграно $$$5$$$ розыгрышей: AABBB. Победителем сета считается игрок B.
  • В пятом сете было сыграно $$$4$$$ розыгрыша: BBAB. Победителем сета считается игрок B.

В итоге первым игроком, выигравшим $$$3$$$ сета, был игрок B. Он и считается победителем игры.