#include<iostream> using namespace std; const int N = 40, M = 1e4 + 10; int w[N], n, f[M]; int main(){ cin >> n; for(int i = 1; i <= 31; i++){ w[i] = i * i; } for(int i = 1; i < M; i++) f[i] = 1e9; for(int i = 1; i <= n; i++){ for(int j = 1; j <= 31 && i - w[j] >= 0; j++){ f[i] = min(f[i], f[i-w[j]] + 1); } } cout << f[n]; return 0; }