E. Это не задача про ним
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Два игрока, Алиса и Боб, играют в игру. У них есть $$$n$$$ куч камней, в $$$i$$$-й куче изначально $$$a_i$$$ камней.

За один ход игрок может выбрать любую кучу камней и забрать из нее любое положительное число камней, с одним условием:

  • пусть текущее количество камней в куче равно $$$x$$$. Нельзя забрать из кучи такое число камней $$$y$$$, что наибольший общий делитель $$$x$$$ и $$$y$$$ не равен $$$1$$$.

Тот игрок, который не может сделать ход, проигрывает. Оба игрока играют оптимально (то есть если у игрока есть стратегия, которая позволяет ему выиграть, как бы оппонент ни сопротивлялся, он выигрывает). Алиса ходит первой.

Определите, кто выиграет.

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

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

Каждый набор входных данных состоит из двух строк:

  • в первой задано одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$);
  • во второй задано $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^7$$$).

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите Alice, если выигрывает Алиса, или Bob, если выигрывает Боб.

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