Два математика играют в следующую игру. Вначале первый
игрок пишет на листке целое число от 2 до N. Затем
второй игрок также пишет число от 2 до N, которое
не имеет общих делителей ни с одним из ранее написанных чисел. Затем то же
самое опять делает первый игрок, и так далее.
Если игрок не может сделать очередной ход, то он
проигрывает.
Требуется определить, который из игроков выиграет, если
известно, что оба они играют оптимально. Если выиграет первый игрок, то
требуется также определить минимальное число, которое он может написать на
первом ходу, чтобы гарантированно победить.
Входные данные содержат единственное целое
число N (2 ≤ N ≤ 100).
Входные данные: в первой строке выведите 1, если
выиграет игрок, который делает первый ход. Если же он не сможет выиграть, то
выведите 0.
В случае, если выигрывает первый игрок, во второй
строке выведите минимальное число, которое он может написать на первом ходу,
чтобы гарантированно победить.
Примеры
|
Входные данные
|
Выходные данные
|
|
6
|
1
2
|
|
3
|
0
|
Пояснение к примеру 1. Если первый игрок напишет число 2, то второй может
написать только 3 или 5. Тогда первый игрок напишет, соответственно, 5 или 3, и
второму будет некуда сходить.
Если
же первый игрок напишет, например, число 5, тогда второй может написать 6 и
выиграет, так как первому будет некуда ходить.
