import math
n = int(input())
dp = [i for i in range(n+1)]
coins = [i for i in range(2, int(math.sqrt(n))+1)]
if coins:
    for coin in coins:
        for j in range(1, n+1):
            if j >= coin ** 2:
                dp[j] = min(dp[j], dp[j-(coin ** 2)] + 1)
    print(dp[n])
else:
    print(n)

# 모든 수는 1의 제곱으로 전부 표현이 가능하므로 dp도 전부 i for i로 디폴트를 설정해준다
# 동전문제의 응용이므로 2부터 해당 숫자의 제곱근까지의 숫자를 coins 배열에 담음
# 찾고자하는 숫자가 2의 제곱인 4보다 작다면 제곱수의 합의 개수를 찾을 필요도 없으므로 그 수를 그대로 출력
# 찾고자하는 숫자가 4보다 크거나 같다면 coins 배열안에 있는 숫자들을 하나씩 꺼내 해당 동전의 제곱보다 큰 수는 동전의 제곱을 뺀 경우보다 1이 많을 것.
# 예를 들면 4의 경우 2의 제곱이므로 4에서 4를 뺀 0을 찾아보면 0은 자연수가 아니므로 쓰인 제곱수도 0. 쓰이는 제곱수는 2의 제곱 하나 뿐이므로 +1을 해주어 4의 경우 쓰이는 제곱수는 1
# 11의 경우 가장 근접한 제곱수는 9. 9는 3의 제곱이므로 dp[9]는 dp[9 - 9] => 즉 dp[0]에 1을 더한 값이므로 dp[9] = 1인데, dp[10]은 dp[1] + 1이므로 2, dp[11]은 dp[2] + 1 이므로 3이다.
#
