你无法想象我们的朋友们在恩沃茨克这个冬天有多冷!其中两个人玩以下游戏来热身:最初一张纸有一个整数 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是一个失败的数字。因此,这一举动将为我们带来胜利。