Problem Description

KC invites his two underlings K and C to play a number game. The game is played in turns, with K going first. KC will first provide a number \( Q \). Each player must replace the current number with one of its factors, but this factor cannot be \( 1 \) or the number itself. For example, if the current number is \( 6 \), then it can be replaced with \( 2 \) or \( 3 \), but not \( 1 \) or \( 6 \). The player who first cannot write any number is declared the winner. Given \( Q \), K wants to know if he can win as the first player, and if so, what is the smallest number he can write to ensure victory? We assume that both K and C are using optimal strategies.

Input Format

A single line containing a positive integer \( Q \).

Output Format

The first line should be either \( 1 \) or \( 2 \), where \( 1 \) indicates that K can win, and \( 2 \) indicates that C can win.

If K can win, the second line should output the smallest number he can write to ensure victory.

If no number can be written initially, the smallest number to ensure victory is considered to be \( 0 \).

Sample Input and Output

Sample Input #1

6

Sample Output #1

2

Sample Input #2

30

Sample Output #2

1
6

Notes/Hints

For \( 30\% \) of the test cases, \( Q \leq 50 \);
For \( 100\% \) of the test cases, \( 2 \leq Q \leq 10^{13} \).

见题面 Input 部分

见题面 Output 部分