数字游戏

题目描述

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

输入输出格式

输入格式


只包括一个正整数Q

输出格式


第一行是1或2,1表示K能胜利,2表示C能胜利。 若K能胜利,则在第二行输出第一次写出的可以制胜的最小数字。 若是第一次就无法写出数字,则认为第一次写出的可以制胜的最小数字为0。

输入输出样例

输入样例 #1

6

输出样例 #1

2

输入样例 #2

30

输出样例 #2

1
6

说明

对于30%的数据,Q<=50; 对于100%的数据,Q<=10^13。