import math

def main():
    N = int(input().strip())
    min_p = N + 1  # Initialize with k=1 case

    # Function to get all divisors of N
    def get_divisors(n):
        divisors = set()
        for i in range(1, int(math.isqrt(n)) + 1):
            if n % i == 0:
                divisors.add(i)
                divisors.add(n // i)
        return sorted(divisors)

    # Handle k=2 case
    divisors = get_divisors(N)
    for m in divisors:
        if m < 2:
            continue
        p_candidate = m - 1
        if p_candidate < 2:
            continue
        if N % m != 0:
            continue
        d = N // m
        if d < p_candidate and d >= 1:
            if p_candidate < min_p:
                min_p = p_candidate

    # Handle k >=3 cases
    max_k = 60  # Sufficiently large to cover possible k values
    for k in range(3, max_k + 1):
        p = 2
        while True:
            # Compute m = (p^k -1) // (p-1)
            try:
                numerator = pow(p, k) - 1
                denominator = p - 1
                if denominator == 0:
                    break  # Avoid division by zero (p=1 is not possible here)
                m = numerator // denominator
            except:
                break  # In case of overflow, though in Python it's unlikely
            if m > N:
                break
            if N % m == 0:
                d = N // m
                if d < p and d >= 1:
                    if p < min_p:
                        min_p = p
            p += 1

    print(min_p)

if __name__ == "__main__":
    main()