11407 - Squares

#include<stdio.h>
#include<math.h>
#define M 10001

int N[M];
int main()
{
    register int n,t,i,j,k;
    //freopen("in.txt","r",stdin);

    //Generate all number of square
    for(i=0;i<M;i++)
        N[i]=M;

    for(i=1;i<=100;i++)
        N[i*i]=1;
    N[1]=1;
    for(i=1;i<M;i++)
    {
        k=i+1;
        for(j=2;k<M;j++)
        {
            if(N[k]>N[i]+1)
                N[k]=N[i]+1;
            k=i+j*j;
        }
    }
    //End of generation

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        printf("%d\n",N[n]);
    }
    return 0;
}