#include<bits/stdc++.h>
using namespace std;
int ans=1e5,n;
int a[30]={0,1,16,81,256,625,1296,2401,4069,6561,10000,14641,20736,28561,38416,50625,65536,83521,104976,130321,160000};
int dfs(int p,int x,int sum){
	if(sum>n||p>ans||x>20||a[x]>n||x<1)return 0;
	else if(sum==n)ans=min(ans,p);
	else{
		ans=min(ans,p+n-sum);
		dfs(p+1,x+1,sum+a[x+1]);
		dfs(p,x+1,sum+a[x+1]-a[x]);
		dfs(p+1,x,sum+=a[x]);
		
	}
	return 0;
}
int main(){
	cin>>n;
	int t=1;
	while(a[t]<=n)++t;
	dfs(1,1,1);
	cout<<ans;
	return 0;
}