#include<bits/stdc++.h> #define int long long using namespace std; int dp[114514],a[105]; signed main(){ int n; cin>>n; for (int i = 0;i <= 101;i++){ a[i] = i * i; } memset(dp,0x7f7f7f7f,sizeof(dp)); dp[0] = 0; for (int i = 1;i <= n;i++){ for (int j = 100;j >= 0;j--){ if (i >= a[j]){ dp[i] = min(dp[i],dp[i - a[j]] + 1); } } } cout<<dp[n]; return 0; }