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()