#include<iostream>
#include<cmath>
using namespace std;
int f(int a)
{
	if(sqrt(a)*sqrt(a)==a)	return 1;
	else
		{
			int mi=100000000;
			for(int j=1;j*j<a;j++)
			{
				mi=min(mi,f(a-j*j));
			}
			return mi+1;
		}
}
int main()
{
	int dp[1000000];
	int n,i,j;
	cin>>n;
	for(i=0;i<=n;i++)
	{
		if(sqrt(i)*sqrt(i)==i)	dp[i]=1;
		else
		{
			int mi=i;
			for(j=1;j*j<=i;j++)
			{
				mi=min(mi,dp[i-j*j]+1);
			}
			dp[i]=mi;
		//	cout<<(dp[i]);
		}
	}
	cout<<dp[n];
}