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

#print(f' sys.getrecursionlimit()={sys.getrecursionlimit()}')
i=0
sys.setrecursionlimit(10000)

@functools.lru_cache()
def f(x):
    global i
    i +=1
    if i%500==0: print(i)
    if x <=1: return 0
    return 1 + min([ f(m + x // m - 2)  for m in range(1,int(sqrt(x))+1) if x%m==0])

x = 2000
t0 = time.clock()
print( f(x))
t1 = time.clock()
print (t1-t0, '  i=', i)