N = int(input())
import sys

if N == 1:
    print(2)
    exit()
if N == 2:
    print(3)
    
C = 10 ** 6 + 1
d = [C] * C

d[1] = 2
d[2] = 3
for i in range(2,C):
    n = 1 + i
    while n < C:
        if i < d[n]:
            d[n] = i
        n = n * i + 1
_min = C
i = 2
while i * i <= N:
    if N % i == 0:
        if d[N//i] < _min:
            _min = d[N//i]
        if d[i] < _min:
            _min = d[i]
    i += 1
if _min == C:
    print(N-1)
else:
    print(_min)