Mathematical game

Consider a mathematical game, two players MDM dylayut moves in turn. Given natural number N. In one move, this number must be reduced by the value of some natural number which does not exceed the value of M so that the result remained non-negative. Losing someone who could not make a move. And the value of M selects a player who goes second. For a given N to find the smallest possible value of M, which gives the second player a real chance to win, or output 0 in a losing case.

Input

One number N (N < 10^5).

Output

One number M - solution to the problem.

Examples