U521565 平方和

**请仔细阅读“题目背景”中的材料，再实现“题目描述”中的问题。** **拉格朗日四平方和定理** > 拉格朗日四平方和定理说明每个正整数均可表示为4个整数的平方和。 它是费马多边形数定理和华林问题的特例。注意有些整数不可表示为 $3$ 个整数的平方和，例如 $15=3^2+2^1+1^1+1^1$。 **费马二平方和定理** > 费马二平方定理是指除了 $2$ 这个特殊的素数，所有的素数都可以分两类：被 $4$ 除余 $1$ 的素数，如 $5,13,17,29,37,41$；第二类则是被 $4$ 除余 $3$ 的素数如$3,7,11,19,23,31$。第一类素数都能表示为两个整数的平方和，第二类都不能。 而对于任意正整数 $n$，满足可分解成二平方数之和的充要条件是 $n$ 经过质因数分解后，对于每个指数为奇数的质数 $p$ 均满足 $p\bmod 4≠3$。如 $490=2^1\times5^1\times7^2$。指数为奇数的项有 $2,5$，它们除以 $4$ 的余数均不为 $3$，故 $490$ 可表示为二平方数之和。实际上，$490=7^2+21^2$。 **勒让德三平方和定理** > 勒让德三平方和定理指出，正整数 $n$ 不能表示成三平方数之和当且仅当 $n=4^a(8k+7)$。在“拉格朗日四平方和定理”中提到的 $15$ 是 $a=0,k=1$ 的情况。

给定一个正整数，求该正整数最少可以表示为多少个正整数的平方和。

**本题含有多组测试数据** 第一行一个整数 $T$，代表数据组数。 接下来 $T$ 行，每行一个整数 $n$。

对于每组测试数据，输出 $n$ 最少可以表示为多少个正整数的平方和。

### 样例解释 $36=6^2$ $7=2^2+1^2+1^2+1^2$ $125=10^2+5^2$ ### 数据范围 **本题使用捆绑测试** | 子任务 | $n\le$ | 特殊性质 | 分值 | | :-----------: | :-----------: | :-----------: | :-----------: | | $0$ | $100$ | 无 | $8$ | | $1$ | $10^{12}$ | A | $2$ | | $2$ | $10^5$ | 无 | $25$ | | $3$ | $10^{12}$ | 无 | $65$ | 特殊性质 A：满足 $n\bmod8=7$。 对于全部数据，满足 $1\le n\le10^{12},1\le T\le10$。