from fractions import gcd

n = int(input())

small = {3 : 2, 5 : 2, 6 : 5, 7 : 6, 10 : 3}


if n in small:
    print(small[n])
else:
    for pot_p in range(int(n**0.5 + 1), n):
        for k in range(2, int(pot_p**0.5 + 1)):
            if pot_p % k == 0:
                break
        else:
            if gcd(pot_p, n) == 1:
                print(pot_p)
                break