#include<stdio.h>
int main()
{
int a[32]={1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841,900,961};
int i,t,j;
int dp[1005];
dp[1]=1;
dp[2]=2;
dp[3]=3;
for(i=4;i<=1000;i++)
{
dp[i]=i;
for(j=0;j<31;j++)
{
if(a[j]<=i && dp[i]>dp[i-a[j]]+1)
dp[i]=dp[i-a[j]]+1;
}
}
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
printf("%d\n",dp[n]);
}
return 0;
}
Arpit's Newsletter read by 15000+ engineers
🔥 Thrice a week, in your inbox, an essay about system design, distributed systems, microservices, programming languages internals, or a deep dive on some super-clever algorithm, or just a few tips on building highly scalable distributed systems.