def fun(i,dp):
        
        
        if(int(i**0.5)==i**0.5):
            return 1
        
        else:
            
            
            temp = 1
            ls = []
            while(temp*temp<i):
                #print(n,temp)
                ls.append(dp[i-(temp*temp)-1])
                temp+=1
            return min(ls)+1
                
        
        
    dp = []
    
    for i in range(1,n+1):
        #print(dp)
        dp.append(fun(i,dp))
        
    return dp[-1]