import sys
import itertools
import numpy as np

def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)
  return divisors
def abc(n):
  b = 2
  fct = [0]
  while b * b <= n:
    while n % b == 0:
      n //= b
      fct.append(b)
    b = b + 1
  if n > 1:
    fct.append(n)
  return fct
def getNearestValue(list, num):
  idx = np.abs(np.asarray(list) - num).argmin()
  return list[idx]
for n in range(2,10**12):
  list_ = abc(n)

  list_.sort()
  tmp = np.sqrt(n)
  N = len(list_)

  dp = [[1 for i in range(N+1)] for j in range(N+1)]

  for i in range(N):
    for j in range(1,N):
      if i == j:
          continue
      else:
        if dp[i][j-1] * list_[j] <= tmp:
          dp[i][j] = dp[i][j-1] * list_[j]
        else:
          continue
  tmplist = list(itertools.chain.from_iterable(dp))

  tmp1 = max(tmplist)
  if tmp1 == 0:
    print(n-1)
    sys.exit()
    
    
  tmp2 = make_divisors(n)
  tmp2.sort()
  sq = np.sqrt(n)
  tmpnum = n
  for i in tmp2:
    if i > sq:
      break
    else:
      tmpnum = min(tmpnum-1, n//i + i - 2)
    
  if (tmp1 - 1)+(n//tmp1-1) != tmpnum:
    print(n)