//1073
#include<iostream>
#include<cmath>
using namespace std;
unsigned long mn;
bool fine;
unsigned long sch(unsigned long n,unsigned long stpos,unsigned long time)
{
    if ((fine==true)&&(time==mn-1)){
        return(1);
    }else{
        n=n-stpos*stpos;
        if (n==0) {
            fine=true;
            return(1);
        }else{
            if (n<(stpos*stpos)) {
                stpos=int(floor(sqrt((long double)n)));
            }
            unsigned long submn,i,tmp;
            submn=sch(n,stpos,time+1);
            for (i=stpos-1;i>0;i--) {
                tmp=sch(n,i,time+1);
                if (tmp<submn) {
                    submn=tmp;
                }
            }
            return(submn+1);
        }
    }
}
int main (void)
{
    unsigned long n,rtfn;
    cin>>n;
    if (n==0) {
        cout<<0;
        return 0;
    }else{
    fine=0;
    rtfn=int(floor(sqrt((long double)n)));
    cout<<sch(n,rtfn,0);
    }
}