← 返回题目列表

Codeforces · 150/A

A. 获胜或冻结

中文机器翻译题面 查看原题

你无法想象我们的朋友们在恩沃茨克这个冬天有多冷!其中两个人玩以下游戏来热身:最初一张纸有一个整数 q。在移动过程中,玩家应该写入任何整数,该整数是最后写入的数字的非平凡除数。那么他应该绕着酒店跑这么多圈。让我们提醒您,如果一个数的除数不同于 1 且不同于被除数本身,则该除数称为非平凡除数。

第一个无法移动的人获胜,因为他继续躺在温暖的床上,盖着三层毯子,而另一个人则继续奔跑。考虑到两名玩家都发挥最佳,确定哪位玩家获胜。如果第一个玩家获胜,则打印任何获胜的第一步。

输入

第一行包含唯一的整数 q (1 ≤ q ≤ 1013)。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 指定器。

输出

在第一行打印获胜玩家的号码(1 或 2)。如果第一个玩家获胜,那么第二行应该包含另一个整数 - 他的第一步(如果第一个玩家甚至无法迈出第一步,则打印 0)。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

6

输出 #1

2

输入 #2

30

输出 #2

1
6

输入 #3

1

输出 #3

1
0

注意

数字6只有两个非平凡因数:2和3。写完数字2和3后不可能再走棋,所以两者都是赢的,因此,数字6是输的数字。玩家可以走一步,在数字 30 之后写下数字 6;众所周知,6是一个失败的数字。因此,这一举动将为我们带来胜利。