#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;
}