def find_min_k():
    N = int(input())
    if N % 3 == 0:
        print(3)
        return
    odd_part = N
    while odd_part % 2 == 0:
        odd_part = odd_part // 2
    if odd_part == 1:
        print(4)
        return
    max_div = int(odd_part ** 0.5) + 1
    for i in range(5, max_div, 2):
        if odd_part % i == 0:
            print(i)
            return
    print(odd_part)

find_min_k()