Алиса и Боб играют в игру.
Они начинают с целого положительного числа \(n\) и поочередно выполняют над ним операции. В свой игрок может вычесть из \(n\) один из его делителей, который не равен \(1\) или \(n\). Игрок, который не может сделать ход в свой ход, проигрывает. Алиса всегда ходит первой.
Обратите внимание, что в каждый ход они вычитают делитель текущего числа.
Вам предлагается выяснить, кто победит в игре, если оба игрока будут играть оптимально.
Выходные данные
Для каждого набора входных данных выведите «Alice», если Алиса выиграет игру, или «Bob», если выиграет Боб, если оба игрока играют оптимально.
Примечание
В первом наборе входных данных игра немедленно заканчивается, потому что Алиса не может сделать ход.
Во втором наборе входных данных Алиса может вычесть \(2\), получив \(n = 2\), тогда Боб не сможет сделать ход, и Алиса выиграет.
В третьем наборе входных данных Алиса может вычесть \(3\), получив \(n = 9\). Единственный ход Боба — вычесть \(3\) и сделать \(n = 6\). Теперь Алиса может снова вычесть \(3\) и получить \(n = 3\). После этого Боб не может сделать ход, и Алиса выигрывает.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
4
12
69
|
Bob
Alice
Alice
Bob
|