Description

KC invited his two underlings, K and C, to play a number game. The game is played by K and C taking turns, with K moving first. KC will first specify a number $Q$. On each move, the player must write a divisor of the current number to replace the current number, but this divisor cannot be $1$ or the number itself. For example, if the current number is $6$, then $2$ and $3$ can be used to replace it, but $1$ and $6$ cannot. The player who first has no number to write is the winner. Given $Q$, K wants to know whether he, as the first player, can win. If he can win, what is the smallest first number he can write that guarantees victory? Assume both K and C play optimally.

Input Format

A single line with a positive integer $Q$.

Output Format

The first line is $1$ or $2$. $1$ means K can win, and $2$ means C can win.

If K can win, then output on the second line the smallest first number he can write that guarantees victory.

If there is no number that can be written on the first move, then the smallest winning first number is considered to be $0$.

6

2

30

1
6

Hint

For 30% of the testdata, $Q \le 50$. For 100% of the testdata, $2 \le Q \le 10^{13}$.

Translated by ChatGPT 5