题目描述

金角大王和银角大王在玩游戏。游戏是金角大王和银角大王轮流操作进行的，金角大王为先手。给定一个数字n，每次操作者必须写出当前数字的一个因数来代替当前数字，但是这个因数不能是1和它本身。例如当前数字为6，那么可以用2, 3来代替，但是1和6就不行。现在规定第一个没有数字可以写出的操作者为胜者。金角大王在已知n的情况，想知道自己作为先手能不能胜利，若能胜利，那么第一次写出的可以制胜的最小数字是多少呢？整个游戏过程我们认为金角大王和银角大王用的都是最优策略。

输入格式

仅一行，一个正整数n。

输出格式

第一行是1或2，1表示金角大王能胜利，2表示银角大王能胜利。
若金角大王能胜利，则在第二行输出第一次写出的可以制胜的最小数字。
若是第一次就无法写出数字，则认为第一次写出的可以制胜的最小数字为0。

样例 #1

样例输入 #1

6

样例输出 #1

2

样例 #2

样例输入 #2

30

样例输出 #2

1
6

提示

对于 $30 \%$ 的数据，$n \le 50$；
对于 $100 \%$ 的数据，$2 \le n \le {10}^{13}$。