# your code goes here
import time
import sys
import functools 
from math import sqrt

#print(f' sys.getrecursionlimit()={sys.getrecursionlimit()}')
i=0
sys.setrecursionlimit(1000000)
#@functools.lru_cache()
#- без нього f(1024)вираховується більше 10 хвилин, а з ним 5 секунд 21:43
@functools.lru_cache(maxsize=None)
def f(x):
    global i
    i +=1
    if i%750==0: print(i)
    if x <=1: return 0
    return 1 + min( [f(m + x // m - 2)  for m in range(int(sqrt(x))+1,0,-1) if x%m==0]  )

x = int(input("дай целое!"))
t0 = time.clock()
print( f(x))
t1 = time.clock()
print (t1-t0, '  i=', i)
print(f.cache_info())