Алиса и Боб играют в игру. В строке $$$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$$$.
Для каждого набора входных данных выведите имя победителя в отдельной строке.
83BRB5RRBBB6RBRBRB8BBRRBRRB6BRRBRB12RBRBRBRBRRBB12RBRBRBRBBBRR4RBBR
Bob Bob Alice Alice Alice Alice Bob Bob
В первом наборе входных данных у Алисы есть два варианта: закрасить первую и вторую клетки или закрасить вторую и третью клетки. Какой бы выбор ни сделала Алиса, после хода Алисы останется ровно одна синяя клетка. Бобу нужно просто закрасить синюю клетку и ее соседнюю, тогда каждая клетка будет белой и Алиса не сможет сделать ход. Итак, Боб — победитель.
Во втором наборе входных данных независимо от того, что выберет Алиса, Боб может закрасить четвертую и пятую клетки за $$$2$$$ хода.
В третьем наборе входных данных сначала Алиса красит третью и четвертую клетки. Неважно, закрашивает ли Боб первую и вторую клетки или пятую и шестую, Алиса может закрасить две другие клетки.
В четвертом наборе входных данных сначала Алиса красит вторую и третью клетки. Если Боб закрашивает пятую и шестую клетки или четвертую и пятую клетки, то Алиса закрашивает седьмую и восьмую клетки. Если Боб закрашивает седьмую и восьмую клетки, то Алиса закрашивает пятую и шестую клетки.
В пятом наборе входных данных Алиса сначала выбирает две средние клетки, затем у Боба, очевидно, есть только два варианта, какой бы вариант он ни выбрал, Алиса может выбрать другой и выиграть.
В восьмом наборе входных данных независимо от того, что выберет Алиса, Боб может выбрать две другие симметричные ячейки.
Название |
---|