C. Игра с картами
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру. У них есть $$$n$$$ карт, пронумерованных от $$$1$$$ до $$$n$$$. В начале игры какие-то из этих карт получает Алиса, остальные — Боб.

Карта под номером $$$i$$$ бьет карту под номером $$$j$$$ тогда и только тогда, когда $$$i \gt j$$$, с одним исключением: карта $$$1$$$ бьет карту $$$n$$$.

Игра идет, пока у каждого из игроков есть хотя бы одна карта. В каждый ход происходит следующее:

  1. Алиса выбирает одну из своих карт и выкладывает ее на стол в открытом виде;
  2. Боб, видя карту Алисы, выбирает одну из своих карт и выкладывает ее на стол в открытом виде;
  3. если карта Алисы бьет карту Боба, обе карты забирает Алиса. Иначе обе карты забирает Боб.

Игрок может использовать карту, которую он забрал на одном из предыдущих ходов.

Проигрывает тот игрок, у которого к началу какого-то хода не окажется ни одной карты. Определите, кто победит, если оба игрока играют оптимально.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк:

  • в первой строке задано одно целое число $$$n$$$ ($$$2 \le n \le 50$$$) — количество карт;
  • во второй строке заданы $$$n$$$ символов, каждый из которых A или B. Если $$$i$$$-й символ A, то карту с номером $$$i$$$ в начале игры получает Алиса, иначе ее получает Боб.

Дополнительное ограничение на входные данные: в каждом наборе входных данных хотя бы одна карта изначально выдается Алисе, и хотя бы одна карта изначально выдается Бобу.

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

Для каждого набора входных данных выведите Alice, если при оптимальной игре победит Алиса, или Bob, если Боб. Можно показать, что если оба игрока играют оптимально, игра обязательно закончится за конечное число ходов победой одного из игроков.

Пример
Входные данные
8
2
AB
2
BA
4
ABAB
4
BABA
3
BAA
5
AAAAB
5
BAAAB
6
BBBAAA
Выходные данные
Alice
Bob
Bob
Bob
Alice
Alice
Bob
Alice
Примечание

В первом наборе входных данных у Алисы только одна карта, и у Боба только одна карта. Поскольку карта Алисы бьет карту Боба, она выигрывает после первого хода.

Во втором наборе входных данных у Алисы только одна карта, и у Боба только одна карта. Поскольку карта Боба бьет карту Алисы, он выигрывает после первого хода.

В третьем наборе входных данных есть два возможных сценария игры:

  • если Алиса сыграет карту $$$1$$$ на первом ходу, Боб может ответить картой $$$2$$$ и забрать обе карты. Тогда Алисе придется сыграть карту $$$3$$$ на втором ходу, и Боб ответит, сыграв карту $$$4$$$. Тогда он выигрывает;
  • если Алиса сыграет карту $$$3$$$ на первом ходу, Боб может ответить картой $$$4$$$ и забрать обе карты. Тогда Алисе придется сыграть карту $$$1$$$, и Боб может ответить либо картой $$$2$$$, либо картой $$$3$$$. Тогда он выигрывает.

В четвертом наборе входных данных есть два возможных сценария игры:

  • если Алиса сыграет карту $$$2$$$ на первом ходу, Боб может ответить картой $$$3$$$ и забрать обе карты. Тогда Алисе придется сыграть карту $$$4$$$ на втором ходу, и Боб ответит, сыграв карту $$$1$$$. Тогда он выигрывает;
  • если Алиса сыграет карту $$$4$$$ на первом ходу, Боб может ответить картой $$$1$$$ и забрать обе карты. Тогда Алисе придется сыграть карту $$$2$$$, и Боб может ответить либо картой $$$3$$$, либо картой $$$4$$$. Тогда он выигрывает.