F. Не очень чётно
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб нашли двоичную$$$^{\text{∗}}$$$ строку $$$s$$$ длины $$$n$$$. Они решили сыграть в игру на этой строке, делая ходы по очереди, начиная с хода Алисы.

На каждом ходу игрок должен выбрать подпоследовательность$$$^{\text{†}}$$$, в которой нечётное количество инверсий $$$^{\text{‡}}$$$ и удалить её. Игрок, который не может сделать ход проигрывает.

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

$$$^{\text{∗}}$$$Двоичная строка — это такая строка, которая состоит только из символов $$$\texttt{0}$$$ и $$$\texttt{1}$$$.

$$$^{\text{†}}$$$Последовательность $$$a$$$ является подпоследовательностью строки $$$b$$$ если $$$a$$$ может быть получена из $$$b$$$ путём удаления нескольких (возможно ни одного или всех) сиволов.

$$$^{\text{‡}}$$$Инверсией в двоичной строке $$$s$$$ называется пара индексов $$$(i, j)$$$, такая что $$$i \lt j$$$, $$$s_i = \texttt{1}$$$ и $$$s_j = \texttt{0}$$$.

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

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

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — длину двоичной строки $$$s$$$.

Вторая строка каждого набора содержит двоичную строку $$$s$$$ длины $$$n$$$. Гарантируется, что $$$s$$$ состоит только из символов $$$\texttt{0}$$$ и $$$\texttt{1}$$$.

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

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

Для каждого набора входных данных выведите $$$\texttt{Alice}$$$, если Алиса выиграет и $$$\texttt{Bob}$$$ иначе.

Пример
Входные данные
3
5
10101
4
0100
6
011001
Выходные данные
Alice
Alice
Bob
Примечание

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

Во втором примере Алиса может выбрать подпоследовательность из индексов $$$1$$$, $$$2$$$, и $$$4$$$, равную $$$\texttt{010}$$$. Остался только символ в позиции $$$3$$$, равный $$$\texttt{0}$$$, осталось $$$0$$$ инверсий. Так что Боб не может выбрать подпоследовательность с нечётным количеством инверсий и Алиса выиграла.

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