CF150A.Win or Freeze

You can't possibly imagine how cold our friends are this winter in Nvodsk! Two of them play the following game to warm up: initially a piece of paper has an integer q. During a move a player should write any integer number that is a non-trivial divisor of the last written number. Then he should run this number of circles around the hotel. Let us remind you that a number's divisor is called non-trivial if it is different from one and from the divided number itself.

The first person who can't make a move wins as he continues to lie in his warm bed under three blankets while the other one keeps running. Determine which player wins considering that both players play optimally. If the first player wins, print any winning first move.

你绝对无法想象今年冬天我们的朋友们在Nvodsk有多冷！其中两人玩下面这个游戏来暖身：初始时，一张纸上写有一个整数 $q$。在每一轮操作中，玩家需写下上一个所写数字的任意一个非平凡因子（non-trivial divisor），然后围绕旅馆跑相应数量的圈。需要提醒的是：若一个数的因子既不等于 $1$，也不等于该数本身，则称其为该数的非平凡因子。

第一个无法进行操作的玩家获胜——他可以继续裹着三层被子躺在温暖的床上，而另一位则不得不持续奔跑。假设双方均以最优策略进行游戏，请判断哪位玩家获胜。若先手玩家获胜，请输出任意一个必胜的首步操作。

The first line contains the only integer q (1 ≤ q ≤ 1013).

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

第一行包含唯一一个整数 $ q $（$ 1 \leq q \leq 10^{13} $）。

在 C++ 中，请勿使用 %lld 格式说明符来读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 格式说明符。

In the first line print the number of the winning player (1 or 2). If the first player wins then the second line should contain another integer — his first move (if the first player can't even make the first move, print 0). If there are multiple solutions, print any of them.

第一行输出获胜玩家的编号（1 或 2）。若第一位玩家获胜，则第二行应输出另一个整数——他的首次移动（若第一位玩家甚至无法进行首次移动，则输出 0）。若存在多种解，输出任意一种即可。

Number 6 has only two non-trivial divisors: 2 and 3. It is impossible to make a move after the numbers 2 and 3 are written, so both of them are winning, thus, number 6 is the losing number. A player can make a move and write number 6 after number 30; 6, as we know, is a losing number. Thus, this move will bring us the victory.

数字 6 只有两个非平凡约数：2 和 3。在写下数字 2 和 3 后，无法再进行任何操作，因此它们均为必胜态，从而数字 6 是一个必败态。玩家可以从数字 30 进行一步操作，写下数字 6；而如前所述，6 是一个必败态。因此，这一步操作将为我们带来胜利。