**update on 2020.6.26**：修改了文章中的一些错误，希望管理员重新审核后通过
-------------
这道题是一道背包题，但有些题解的解释不是非常详细，所以我写了一篇题解来帮助像我一样的蒟蒻
思路：$dp[i][j]$代表 $i$用$j$个平方数所可以组成的方案数，这样对于一个$n$，只要输出 $dp[n][1-4]$的和就行了。
那么怎么计算呢？因为每个数可以用无数次，所以使用类似完全背包的方法（如果你不知道什么是完全背包，请看[这道题](https://www.luogu.org/problemnew/show/P1616)），因为每个数$n$都可以由$n$减去一个平方数可得，则可以推出$dp[i][j]+=dp[i-k*k][j-1]$
这样就可以写出代码了：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int M=32768;
int t,n;
int dp[33000][5]={1};//注意，dp[0][0]要设为1，否则会全输出0
int main()
{
for (int i=1;i*i<=M;i++)//枚举所有平方数
for (int j=i*i;j<=M;j++)//因为j-i*i要>=0(否则会RE)，所以直接从i*i开始
for (int sum=1;sum<=4;sum++)//枚举使用次数
dp[j][sum]+=dp[j-i*i][sum-1];//计算
cin>>t;
while(t--)//循环t次
{
int n,ans=0;
cin>>n;
for (int i=1;i<=4;i++)
ans+=dp[n][i];
cout<<ans<<endl;
}
return 0;
}
```