Алиса и Боб играют в игру. У них есть доска; изначально на ней написано \(n\) целых чисел, каждое из которых равно \(1\).
Алиса и Боб ходят по очереди; первым ходит Алиса. В свой ход игрок должен выбрать несколько (как минимум два) равных чисел на доске, стереть их и написать новое число, равное их сумме.
Например, если на доске сейчас написаны числа \(\{1, 1, 2, 2, 2, 3\}\), то возможны следующие ходы:
- выбрать два числа, равных \(1\), стереть их и написать число \(2\), тогда доска станет \(\{2, 2, 2, 2, 3\}\);
- выбрать два числа, равных \(2\), стереть их и написать число \(4\), тогда доска станет \(\{1, 1, 2, 3, 4\}\);
- выбрать три числа, равных \(2\), стереть их и написать число \(6\), тогда доска станет \(\{1, 1, 3, 6\}\).
Если игрок не может сделать ход (все числа на доске различны), то этот игрок выигрывает в игре.
Определите, кто выиграет, если оба игрока будут играть оптимально.
Выходные данные
Для каждого теста выведите Alice, если Алиса выиграет (с учетом того, что оба игрока будут играть оптимально). Иначе выведите Bob.
Примечание
В первом наборе входных данных \(n = 3\), поэтому на доске изначально написаны числа \(\{1, 1, 1\}\). Мы можем показать, что Боб всегда может выиграть. У Алисы есть два возможных первых хода:
- если Алиса выбирает два числа, равных \(1\), стирает их и пишет \(2\), то доска становится \(\{1, 2\}\). Боб не может сделать ход, поэтому он выигрывает;
- если Алиса выбирает три числа, равных \(1\), стирает их и пишет \(3\), то доска становится \(\{3\}\). Боб не может сделать ход, поэтому он выигрывает.
Во втором наборе входных данных \(n = 6\), поэтому на доске изначально написаны числа \(\{1, 1, 1, 1, 1, 1\}\). Алиса может выиграть, например, выбрав на первом ходу два числа, равных \(1\), стерев их и написав \(2\). Тогда доска станет \(\{1, 1, 1, 1, 2\}\), и у Боба будет три возможных ответных хода:
- если Боб выберет четыре числа, равных \(1\), сотрет их и напишет \(4\), то доска станет \(\{2,4\}\). Алиса не может сделать ход, поэтому она выигрывает;
- если Боб выберет три числа, равных \(1\), сотрет их и напишет \(3\), то доска станет \(\{1,2,3\}\). Алиса не может сделать ход, поэтому она выигрывает;
- если Боб выберет два числа, равных \(1\), сотрет их и напишет \(2\), то доска станет \(\{1, 1, 2, 2\}\). Алиса может продолжить, например, выбрав два числа, равных \(2\), стерев их и написав \(4\). Тогда доска станет \(\{1,1,4\}\). Единственный возможный ответ для Боба — выбрать два числа, равных \(1\), и написать вместо них \(2\); тогда доска станет \(\{2,4\}\), Алиса не может сделать ход, поэтому она выигрывает.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3
6
|
Bob
Alice
|