Prime Stone Game: Minimum Moves to Win

There are several stones on the table. Two players take turns removing stones. In each move, a player is allowed to remove a number of stones equal to a prime number. A move counts as one step. If a player cannot make a move (i.e. there is no prime number ≤ the number of remaining stones), that player loses.

Under the assumption that both players play optimally, the winning player will try to finish the game as quickly as possible, while the losing player will try to delay defeat as long as possible. Given the initial number of stones, determine the minimum number of moves needed for the winning player to secure victory. If there is no winning strategy for the first player, output -1.

Note: A move subtracts p stones where p is a prime number and must satisfy p ≤ n. The base condition is when n < 2 (since the smallest prime is 2), in which case the current player loses.

The recurrence relation for the game is defined as follows: For a state with n stones, if there exists a prime p (with p ≤ n) such that the state n - p is losing for the opponent, then the current state is winning and the game can be finished in 1 move. Otherwise, the state is losing for the current player.

In summary, given an integer n, output 1 if there is a winning move (i.e. if a prime p exists with n - p < 2 or more generally leading to a losing state for the opponent), otherwise output -1.

Mathematically, if we define a function \( f(n) \) that returns the minimum moves required to win when the current player is in state \( n \) (and returns -1 if the state is losing), then

\[ f(n) = \begin{cases} -1, & n < 2, \\ 1, & \text{if there exists a prime } p \le n \text{ such that } f(n-p) = -1, \\ -1, & \text{otherwise.} \end{cases} \]

inputFormat

The input consists of a single integer n (0 &le n &le 10^5), which represents the initial number of stones on the table.

outputFormat

Output a single integer which is the minimum number of moves required to win if the first player has a winning strategy. If the first player cannot force a win (i.e. the position is losing), output -1.

sample

1

-1