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