A. Победи или замерзни
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Вы даже не представляете себе, как же холодно нашим друзьям этой зимой в городе XXXводске! Чтобы согреться, двое из них играют в следующую игру. Изначально на бумажке написано одно целое число q. Своим ходом игрок должен написать любое число, являющееся нетривиальным делителем последнего из написанных чисел, после чего он должен столько раз пробежать вокруг гостиницы. Напоминаем, что делитель числа называется нетривиальным, если он отличен от единицы и от самого делимого числа.

Тот, кто первым не может сделать ход, выигрывает, так как он остается лежать в теплой кроватке под тремя одеялами, пока другой еще наворачивает круги. Определите, кто выигрывает при оптимальной игре обоих, и, если выигрывает первый игрок, то выведите любой выигрышный первый ход.

Входные данные

В первой строке записано единственное целое число q (1 ≤ q ≤ 1013).

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Выходные данные

В первой строке выведите номер игрока-победителя (1 или 2). Если побеждает первый игрок, то во второй строке должно находиться еще одно целое число — его первый ход (если первый игрок не может сделать даже первый ход, выведите 0). Если решений несколько, выведите любое.

Примеры
Входные данные
6
Выходные данные
2
Входные данные
30
Выходные данные
1
6
Входные данные
1
Выходные данные
1
0
Примечание

Число 6 имеет только два нетривиальных делителя: 2 и 3. Из чисел 2 и 3 ходов сделать уже нельзя, поэтому они оба являются выигрышными, а значит число 6 проигрышное. Из числа 30 можно сделать ход в число 6, которое, как мы уже знаем, проигрышное, значит этот ход принесет нам победу.