Алиса и Боб играют в игру на массиве $$$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», если выигрывает Боб. Оценщик чувствителен к регистру.
41010 9 8 7 6 5 4 3 2 131 8192 67726 526 7
AliceBobAliceBob
В первом наборе входных данных Алиса выиграет, если оба игрока будут играть оптимально.
Во втором наборе входных данных Боб всегда может выиграть, независимо от того, какие ходы делает Алиса.
В третьем наборе входных данных Алиса может выиграть, заменив $$$6$$$ на $$$3$$$ и $$$2$$$.
В четвёртом тестовом случае игра заканчивается немедленно, и Боб побеждает.
| Codeforces Round 1084 (Div. 3) |
|---|
| Закончено |
