Mathematical game#1361

Mathematical game

1 second

64 megabytes

Easy

Consider a mathematical game in which two players take turns making moves. A natural number $N$ is given. On each turn, a player must decrease this number by a natural number that does not exceed $M$ , making sure the result remains non-negative. The player who cannot make a move loses. The value $M$ is chosen by the player who goes second. For the given $N$ , find the smallest possible value of $M$ that gives the second player a real chance to win, or output $0$ if it is not possible.

Input

One number $N$ , $N < 1 0^{5}$ N < 10^5.

Output

One number $M$ – solution to the problem.

Examples

Example 1

Loading

N < 1 0^{5}