Mathematical game

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.


One numberN (N < 105).


One number M - solution to the problem.

Time limit 1 second
Memory limit 64 MiB
Input example #1
Output example #1