费马四平方数猜想指出，任意自然数都可以分解成不超过四个完全平方数的和。
例如：144 = 122 ，14 = 12 + 22 +
32。
32。
现在给出自然数N（N ≤ 60000），_gXX希望知道N最少可以分解成多少个完全平方数。
Input
输入文件包含多组数据。
第一行，一个整数T（T ≤ 10000），表示数据的组数。
第2~T+1行，每行一个自然数N。
Output
对于每组数据输出一个自然数，表示自然数N最少可以分解成多少个完全平方数。
Sample Input
1 144
Sample Output
1
#include<stdio.h>
#include<math.h>
int main()
{
int m,N,s[60005];
for(int i=0;i<=60001;i++)s[i]=4;//先初始每个数是最多由4个平方数组成
for(int i=0;i*i<=60001;i++)s[i*i]=1;//只有一个平方数
for(int i=1;i<=60000;i++)//二个平方数由两个一个平方数组成，三个平方数由一个平方数和一个由两个平数数组成
if(s[i]==1)
{
for(int j=1;j+i<=60000;j++)
if(s[i+j]>s[j]+1)
s[i+j]=s[j]+1;
}
scanf("%d",&m);
while(m--)
{
scanf("%d",&N);
printf("%d\n",s[N]);
}
}