# 17626번
# 1 <= n <= 50000
# 제곱수로 나타내기
# 내 생각엔 입력된 수에 제곱근을 구해서 그 값을 정수로 바꾸고
# 그 값을 뺀 값에 제곱근을 구해서 다시 빼고 뭐 그런식으로 하면 되지 않을까
# 음 아니었음 무조건 큰 수를 빼는 것이 답이 아니네 Dp인가?
# 1 1개 2 2개 3 3개 4 1개 5 2개 6 3개 7 4개 8 2개 
# 9 1개 10 2개 11 3개 12 3개 13 2개 14 3개 15 4개 16 1개 17 2개
# 18 3개 19 4개 20 2개 21 3개 22 3개 23 4개 24 3개 25 1개 
# d[n] = min(d[n보다 작은 제곱수 계속 -1]+d[n-제곱수])
import math

natural = [i**2 for i in range(1,224)]
n = int(input())
d = [4 for _ in range(50000)]
d[0] = 1; d[1] = 2; d[2] = 3
for i in natural:
    d[i-1] = 1

for i in range(4,n):
    for j in range(int(math.sqrt(i))-1,0,-1):
        if d[natural[j]-1] + d[i-natural[j]] < d[i]:
            d[i] = d[natural[j]-1] + d[i-natural[j]] 
            
print(d[n-1])