def base_k(num, k): result = set() while num > 0: amari = num%k result.add(amari) num -= amari num //= k return len(result) def divisors(n): lower_divisors , upper_divisors = [], [] i = 1 while i*i <= n: if n % i == 0: lower_divisors.append(i) if i != n // i: upper_divisors.append(n//i) i += 1 return lower_divisors + upper_divisors[::-1] N = int(input()) if N <= 2: print(N+1) exit() for i in range(2, min(1001, N)): if base_k(N, i) == 1: #print(i, calc) print(i) exit() divs = divisors(N) for d in divs: if d < min(1001, N): continue calc = base_k(N, d-1) if calc == 1: #print(d-1, calc) print(d-1) exit()