#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
int vis[100007];
int main(){

  queue<int> q;
  int n;
  cin>>n;
  q.push(n);
  memset(vis,-1,sizeof vis);
  vis[n]=0;
  while(!q.empty())
  {

      int x=q.front();
      q.pop();
      for(int i=1;i*i<=x;i++)
      {
          int y=x-i*i;
          if(vis[y]!=-1)continue;
          vis[y]=vis[x]+1;
          q.push(y);
          if(y==0)
          {
              cout<<vis[y];
              return 0;
          }

      }
  }
    return 0;
}