Два игрока, Алиса и Боб, играют в игру. У них есть \(n\) куч камней, в \(i\)-й куче изначально \(a_i\) камней.
За один ход игрок может выбрать любую кучу камней и забрать из нее любое положительное число камней, с одним условием:
- пусть текущее количество камней в куче равно \(x\). Нельзя забрать из кучи такое число камней \(y\), что наибольший общий делитель \(x\) и \(y\) не равен \(1\).
Тот игрок, который не может сделать ход, проигрывает. Оба игрока играют оптимально (то есть если у игрока есть стратегия, которая позволяет ему выиграть, как бы оппонент ни сопротивлялся, он выигрывает). Алиса ходит первой.
Определите, кто выиграет.
Выходные данные
Для каждого набора входных данных выведите Alice, если выигрывает Алиса, или Bob, если выигрывает Боб.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
3 2 9
4
3 3 6 1
5
1 2 3 4 5
|
Bob
Alice
Bob
|