#include<bits/stdc++.h> using namespace std; int a,len; int main(){ cin>>a; vector<int>b; len=sqrt(a); for(int i=1;i<=len;i++) b.push_back(i*i); vector<int>dp(a+1,INT_MAX); dp[0]=0; for(int i=1;i<=len;i++) for(int j=b[i-1];j<=a;j++) if(dp[j-b[i-1]]<INT_MAX) dp[j]=min(dp[j],dp[j-b[i-1]]+1); cout<<dp[a]; }