完美平方

题目描述:

      任何一个数都可以被表示为若干个完全平方数（完全平方数指根号后为整数的数，例如9,25,36,100等）之和，例如：12可以表示为4+4+4,13可以表示为9+4。现在一共有n个数 $a_1,a_2,a_3,\dots a_{n-1},a_n$ 。请你求出每个数最少可以分解为多少个完全平方数之和。

输入格式:

      第一行一个正整数$n$，意义同题目。

      随后$n$行，每行一个正整数，第 $i+1$行的数表示题目中的 $a_i$ _。

输出格式:

      共$n$行，第$i$行表示$a_i$的最少完全平方数之和的个数。

样例输入:

3
12
13
39

样例输出:

3
2
4

提示:

样例解释：

12=4+4+4;

13=4+9;

39=25+9+4+1;（有多种方式）

对于10%的数据，n<=20;

对于30%的数据，n<=100;

对于55%的数据，n<=200，所有的ai都保证：0<a_i<=20000;

对于100%的数据，n<=50000，所有的ai都保证：0<a_i<=400000;

本题是给对于做不出超难动规想刷水题或者初学动规的的奆佬们刷题用的。

时间限制: 2000ms
空间限制: 256MB

---

来源: by zhr