Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

H. Игра в простые разделения
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру с $$$n$$$ кучками камней, где $$$i$$$-я кучка содержит $$$a_i$$$ камней. Игроки делают ходы по очереди, причем Алиса ходит первой.

На каждом ходу игрок выполняет следующие три шага:

  1. Выбирает целое число $$$k$$$ ($$$1 \leq k \leq \frac n 2$$$). Обратите внимание, что значение $$$k$$$ может быть разным для разных ходов.
  2. Удаляет $$$k$$$ куч камней.
  3. Выбирает еще $$$k$$$ кучек камней и разделяет каждую кучку на две кучки. Количество камней в каждой новой куче должно быть простым числом.

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

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

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — количество камней в кучах.

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

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

Для каждого набора входных данных выведите «Alice» (без кавычек), если Алиса выиграет, и «Bob» (без кавычек) в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «alIcE», «Alice» и «alice» будут считаться одинаковыми.

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

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

Во втором наборе входных данных есть $$$3$$$ кучи камней с $$$3$$$, $$$5$$$ и $$$7$$$ камнями соответственно. Алиса может выбрать $$$k = 1$$$, удалить кучу из $$$7$$$ камней, а затем разделить кучу из $$$5$$$ камней на две кучи камней с простыми количествами $$$2$$$ и $$$3$$$. В итоге получится $$$3$$$ кучки камней с $$$3$$$, $$$2$$$ и $$$3$$$ камнями соответственно, в результате чего у Боба не остается ни одного допустимого хода, и Алиса выигрывает.

В третьем наборе входных данных есть $$$4$$$ кучи камней с $$$4$$$, $$$6$$$, $$$8$$$ и $$$10$$$ камнями соответственно. Алиса может выбрать $$$k = 2$$$ и удалить две кучи камней $$$8$$$ и $$$10$$$. Далее она делит кучу камней $$$4$$$ на две кучи камней с простыми количествами $$$2$$$ и $$$2$$$, а кучу камней $$$6$$$ — на две кучи камней $$$3$$$ и $$$3$$$. После этого у Боба не остается допустимых ходов, и Алиса выигрывает.

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