ЗАДАЧА E
Еще одна игра
| Имя входного файла: | game2.in |
| Имя выходного файла: | game2.out |
| Ограничение по времени: | 1 секунда |
| Ограничение по памяти: | 64 Мб |
Тут в дверь постучали. Хватайка спрашивает:
- Кто там?
Из-за двери отвечают:
- Свои.
Кот говорит:
- В такую погоду свои дома сидят. Телевизор смотрят. Только чужие шастают. Не будем дверь открывать!
Э.Успенский «Дядя Федор, пес и кот», глава 21
После того, как Шарик обзавелся программой для игры в настольные игры со стрелками, соревноваться с ним стало абсолютно бесполезно. Ведь он сразу же может сказать, кто выиграет в партии. Но до конца зимы оставалось еще больше месяца, а потому нужно было коротать долгие вечера за каким-нибудь занятием. Поэтому дядя Федор предложил Матроскину и Шарику новую игру.
Новая игра – исключительно интеллектуальная и проводится над заранее заданным числом N. Матроскин и Шарик по очереди делают ходы. За один ход игрок может выполнить ровно одно из следующих двух действий: либо некоторое ненулевое количество раз поделить данное число на любое простое число, при условии, что результат будет выражаться целым числом, либо умножить данное число некоторое число раз на любое простое число. Проигрывает тот, кто не может сделать ход. Так как при таких правилах игра может вообще не закончиться, Матроскин и Шарик договорились, что количество ходов для каждого игрока, в которых число было умножено, должно быть не больше K.
Хитрый Шарик опять просит вас определить, кто выиграет при оптимальной игре обоих игроков.
Входные данные
Единственная строка входного файла содержит два целых числа N и K (1 <= N <= 1012, 0 <= K <= 1012).
Выходные данные
Если игрок, который первым делает ход, побеждает при правильной игре, то в единственную строку выходного файла выведите 1. Если же побеждает второй игрок, то выведите 2.
Пример
| game2.in | game2.out |
|---|---|
|
|