### 问题描述

小舟和小渡玩一种游戏。游戏是两人轮流操作进行的，小舟先手。

游戏开始时，有一个数字 $Q$，每次操作玩家必须写出当前数字的一个因数来代替当前数字，但是这个因数不能是 $1$ 和数字本身。

例如，当前数字为 $6$，那么可以用 $2$ 和 $3$ 来代替，但是 $1$ 和 $6$ 就不行。

游戏规定，第一个没有数字可以写出的玩家即为胜者。假设小舟和小渡都将使用最优策略进行游戏，请你判断小舟作为先手能否胜利。若可以，请你求出小舟第一次写出的可以制胜的数字的最小值。

输入格式

输入一个正整数 $Q$。

输出格式

第一行输出 $1$ 或者 $2$，$1$ 表示小舟可以胜利，$2$ 表示小渡可以胜利。

若小舟可以胜利，那么在第二行输出第一次写出的可以制胜的最小数字。

若是第一次就无法写出数字，则认为第一次写出的可以制胜的最小数字为 $0$。

样例输入

30

样例输出

1
6

评测数据规模

对于所有评测数据，$2\leq{Q}\leq{10^{13 }}$。