HS09EQ - Diophantine equation

Sometimes solving a Diophantine equation is very hard. But, for example, the equation a+b2+c3+d4=n has a trivial solution for every value of n. Your task is to determine the number of solutions of the equation for each given n, assuming that in the equation all the values a, b, c and d are non-negative integers.

Input

The first line of input contains an integer T, representing the number of test cases (T<20000).

The following T lines contain one non-negative integer n each, where n < 109.

Output

Output T lines, each containing the number of solutions of the respective equation for n.

Example

Input:
5
0
1
10
100
1000

Output:
1
4
19
148
1476

Added by:Robert Gerbicz
Date:2009-09-07
Time limit:1s-4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 C++ 4.3.2 CLOJURE ERL JS-RHINO NODEJS PERL6 SCALA
Resource:High School Programming League

hide comments
2010-07-23 19:29:27 cegprakash
hai i tried to solve the problem directly.
but my time limit got exceeded.
Is there any formula or any techniques to find the no. of soln.s??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.