KC's Number Game

KC invites his two underlings, K and C, to play a number game. The game proceeds as follows: KC provides an initial number \(Q\). The two players, with K moving first, take turns replacing the current number with one of its proper divisors, where a proper divisor is defined as a divisor that is neither 1 nor the number itself. For example, if the current number is \(6\), the only valid moves are \(2\) and \(3\>.

The twist is that the first player who is unable to make a move wins the game. In other words, if the current number has no valid proper divisors when it is a player's turn, that player wins immediately.

Given \(Q\), determine whether K (the first player) can guarantee a win assuming both players play optimally. If K can force a win, output the smallest number he can write on his first move that will guarantee victory. Note that if \(Q\) has no valid moves (that is, if \(Q\) is prime or has no proper divisors), then K wins immediately and you should output 0. If K cannot force a win, output -1.

inputFormat

The input consists of a single integer \(Q\) representing the initial number.

outputFormat

Output a single integer. If K can force a win, output the smallest winning first move, or 0 if no valid move exists (i.e. \(Q\) has no proper divisors). Otherwise, output -1.

sample

4

-1