|
Три поросенка
(Время: 1 сек. Память: 16 Мб Сложность: 71%)
Три поросенка играют в следующую игру.
Первый поросенок придумывает натуральное число N1 и сообщает его второму поросенку. После этого второй поросенок придумывает такое натуральное число N2, что существуют такие A1 ≥ 2, B1 ≥ 2, что N2 = A1 + B1 и A1 x B1 = N1, и сообщает его третьему поросенку. Тот аналогично придумывает число N3 и сообщает его первому поросенку, и т.д.
Если какой-нибудь поросенок называет число Ni, для которого следующий поросенок не может придумать числа Ai и Bi, то он выигрывает. Если же игра никогда не заканчивается, то считается, что наступила ничья.
Дано число N. Определите, кто выигрывает, если первый поросенок начинает и придумывает число N.
Поросята играют оптимально. То есть, если для поросенка существует ход, приводящий к его выигрышу, то он его делает; если такого хода не существует, но существует ход, ведущий к ничье, то поросенок делает этот ход; иначе, он делает ход, максимизирующий его число Ni.
Входные данные
Входной файл INPUT.TXT содержит натуральное число N (2 ≤ N ≤ 106).
Выходные данные
В выходной файл OUTPUT.TXT выведите порядковый номер поросенка, выигрывающего игру, или 0, если наступает ничья.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 5 | 1 |
2 | 16 | 3 |
3 | 4 | 0 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |