#include<bits/stdc++.h> using namespace std; int n,top; int a[10005],que[10005]; bool cmp(int x,int y){return x>y;} int main(){ cin>>n; int m=sqrt(n); if(m*m==n)return cout<<"1",0; for(int i=1;i*i<n;i++){ a[++top]=i*i; } sort(a+1,a+top+1,cmp); for(int i=1;i<=top;i++)que[a[i]]=1; for(int ans=2;;ans++){ for(int i=1;i<=top;i++){ for(int j=1;j<=min(ans*a[1],n),j+a[i]<=n;j++){ if(que[j]==ans-1)que[j+a[i]]=ans; } } if(que[n])return cout<<ans,0; } }