E. Делительная битва
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру на массиве $$$a$$$, изначально содержащем $$$n$$$ положительных целых чисел, при этом ходит Алиса первой.

В каждом ходе игрока, если $$$a$$$ не убывающий$$$^{\text{∗}}$$$, игра немедленно заканчивается. В противном случае игрок может выбрать элемент $$$x$$$ из массива и положительные целые числа $$$1 \lt y,z \lt x$$$, такие что $$$x=yz$$$, и заменить $$$x$$$ в массиве на два элемента $$$y$$$ и $$$z$$$ (в любом порядке в исходном местоположении $$$x$$$). Если такой ход невозможен, игра заканчивается.

Как только игра заканчивается, если $$$a$$$ не убывающий, то Боб выигрывает. В противном случае выигрывает Алиса. Определите, кто выиграет игру, если оба игрока играют оптимально.

$$$^{\text{∗}}$$$$$$a$$$ не убывающий, если $$$a_i\leq a_{i+1}$$$ для всех $$$1\leq i\leq m-1$$$, где $$$m$$$ — длина $$$a$$$.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$).

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$.

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

Для каждого набора входных данных выведите строку, содержащую «Alice», если выигрывает Алиса, или «Bob», если выигрывает Боб. Оценщик чувствителен к регистру.

Пример
Входные данные
4
10
10 9 8 7 6 5 4 3 2 1
3
1 8192 677
2
6 5
2
6 7
Выходные данные
Alice
Bob
Alice
Bob
Примечание

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

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

В третьем наборе входных данных Алиса может выиграть, заменив $$$6$$$ на $$$3$$$ и $$$2$$$.

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