#include<bits/stdc++.h> using namespace std; int coin[100001],dp[10001]; int main(){ memset(dp,0x3f3f3f,sizeof(dp)); dp[0]=0; int n,amount; cin>>amount; for(int i=1;i*i<=amount;i++){ coin[i]=i*i; n=i; } for(int i=1;i<=n;i++){ for(int j=coin[i];j<=amount;j++){ if(coin[j]!=0x3f3f3f){ dp[j]=min(dp[j],dp[j-coin[i]]+1); } } } cout<<(dp[amount]>amount?-1:dp[amount]); return 0; }