Вы даже не представляете себе, как же холодно нашим друзьям этой зимой в городе XXXводске! Чтобы согреться, двое из них играют в следующую игру. Изначально на бумажке написано одно целое число q. Своим ходом игрок должен написать любое число, являющееся нетривиальным делителем последнего из написанных чисел, после чего он должен столько раз пробежать вокруг гостиницы. Напоминаем, что делитель числа называется нетривиальным, если он отличен от единицы и от самого делимого числа.
Тот, кто первым не может сделать ход, выигрывает, так как он остается лежать в теплой кроватке под тремя одеялами, пока другой еще наворачивает круги. Определите, кто выигрывает при оптимальной игре обоих, и, если выигрывает первый игрок, то выведите любой выигрышный первый ход.
Выходные данные
В первой строке выведите номер игрока-победителя (1 или 2). Если побеждает первый игрок, то во второй строке должно находиться еще одно целое число — его первый ход (если первый игрок не может сделать даже первый ход, выведите 0). Если решений несколько, выведите любое.
Примечание
Число 6 имеет только два нетривиальных делителя: 2 и 3. Из чисел 2 и 3 ходов сделать уже нельзя, поэтому они оба являются выигрышными, а значит число 6 проигрышное. Из числа 30 можно сделать ход в число 6, которое, как мы уже знаем, проигрышное, значит этот ход принесет нам победу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
|
2
|
|
2
|
30
|
1
6
|
|
3
|
1
|
1
0
|