F. Игра-раскраска
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру. В строке $$$n$$$ ячеек. Изначально каждая ячейка либо красная, либо синяя. Алиса ходит первой.

На каждом ходу Алиса выбирает две соседние клетки, в которых есть хотя бы одна красная клетка, и окрашивает эти две клетки в белый цвет. Затем Боб выбирает две соседние клетки, содержащие хотя бы одну синюю клетку, и окрашивает эти две клетки в белый цвет. Игрок, который не может сделать ход, проигрывает.

Определите победителя, если и Алиса, и Боб играют оптимально.

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

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

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

Для каждого набора входных данных первая строка содержит целое число $$$n$$$ ($$$2 \leq n \leq 5 \cdot 10^5$$$) — количество ячеек.

Вторая строка содержит строку $$$s$$$ длины $$$n$$$ — начальное состояние ячеек. $$$i$$$-я ячейка красная, если $$$s_i = $$$R, и синяя, если $$$s_i = $$$B.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.

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

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

Пример
Входные данные
8
3
BRB
5
RRBBB
6
RBRBRB
8
BBRRBRRB
6
BRRBRB
12
RBRBRBRBRRBB
12
RBRBRBRBBBRR
4
RBBR
Выходные данные
Bob
Bob
Alice
Alice
Alice
Alice
Bob
Bob
Примечание

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

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

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

В четвертом наборе входных данных сначала Алиса красит вторую и третью клетки. Если Боб закрашивает пятую и шестую клетки или четвертую и пятую клетки, то Алиса закрашивает седьмую и восьмую клетки. Если Боб закрашивает седьмую и восьмую клетки, то Алиса закрашивает пятую и шестую клетки.

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

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