文理学院程序设计在线练习


四平方和定理

Time Limit: 2 Second(s)    Memory Limit: 32 MB

Total Submission(s): 76   Accepted Submission(s): 19
Problem Description

四平方和定理是这样描述的:任何一个正整数都可以表示成不超过四个整数的平方之和。

关于四平方定理的明确表述最早出现在法国数学家 Claude Bachet 对 Diophantus 的 《算术》 所作的一段注释中,但是直到1770年,才由法国数学家 Joseph Lagrange 率先给出了四平方定理的证明,这一定理因此而被称为 Lagrange 四平方和定理。

这个定理告诉我们,任何一个正整数可以表示成1个、2个、3个、最多不超过4个整数的平方之和。

这里请你编程进行进一步验证,对于给定的正整数n,最少可以表示成几个整数的平方和。

Input

输入数据首先包含一个整数T(1<=T<=1000),表示测试实例的个数,然后是T组测试数据。每组包括1个正整数n(n<=50000)。

Output

对于每组测试,输出最少可以表示成几个整数的平方和。

Sample Input
3
1
10
70
Sample Output
1
2
3
Author

flx

Source

usx第八届程序设计竞赛