#include<bits/stdc++.h>
using namespace std;
vector<int> v;
int f[100010];//总和为i需要的完全平方数的最小数量
int dfs(int k) { //总和为k的完全平方数的最小数量
	int sq = sqrt(k);
	if (f[k] != 0) {
		return f[k];//如果之前递归过了，直接返回缓存过的答案
	}
	if (sq * sq == k) {
		return f[k] = 1;
	}
	int res = INT_MAX;
	for (int i = 0; i < v.size() && v[i] <= k; i++) {
		res += min(res, dfs(v[i]) + dfs(k - v[i]));//任意数都能表示为完全平方数+另一个数字
	}
	return f[k] = res;
}
int main() {
	int n;
	for (int i = 1; i * i <= 100000; i++) {
		v.push_back(i*i);
	}
	cin >> n;
	cout << dfs(n);
	return 0;
}//记忆化搜索
//睿智的数学发现