# 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())
IyB5b3VyIGNvZGUgZ29lcyBoZXJlCmltcG9ydCB0aW1lCmltcG9ydCBzeXMKaW1wb3J0IGZ1bmN0b29scyAKZnJvbSBtYXRoIGltcG9ydCBzcXJ0CgojcHJpbnQoZicgc3lzLmdldHJlY3Vyc2lvbmxpbWl0KCk9e3N5cy5nZXRyZWN1cnNpb25saW1pdCgpfScpCmk9MApzeXMuc2V0cmVjdXJzaW9ubGltaXQoMTAwMDAwMCkKI0BmdW5jdG9vbHMubHJ1X2NhY2hlKCkKIy0g0LHQtdC3INC90YzQvtCz0L4gZigxMDI0KdCy0LjRgNCw0YXQvtCy0YPRlNGC0YzRgdGPINCx0ZbQu9GM0YjQtSAxMCDRhdCy0LjQu9C40L0sINCwINC3INC90LjQvCA1INGB0LXQutGD0L3QtCAyMTo0MwpAZnVuY3Rvb2xzLmxydV9jYWNoZShtYXhzaXplPU5vbmUpCmRlZiBmKHgpOgogICAgZ2xvYmFsIGkKICAgIGkgKz0xCiAgICBpZiBpJTc1MD09MDogcHJpbnQoaSkKICAgIGlmIHggPD0xOiByZXR1cm4gMAogICAgcmV0dXJuIDEgKyBtaW4oIFtmKG0gKyB4IC8vIG0gLSAyKSAgZm9yIG0gaW4gcmFuZ2UoaW50KHNxcnQoeCkpKzEsMCwtMSkgaWYgeCVtPT0wXSAgKQoKeCA9IGludChpbnB1dCgi0LTQsNC5INGG0LXQu9C+0LUhIikpCnQwID0gdGltZS5jbG9jaygpCnByaW50KCBmKHgpKQp0MSA9IHRpbWUuY2xvY2soKQpwcmludCAodDEtdDAsICcgIGk9JywgaSkKcHJpbnQoZi5jYWNoZV9pbmZvKCkp