P2092 Number Game

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.

A single line with a positive integer $Q$.

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$.

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