HS09EQ  Diophantine equation
Sometimes solving a Diophantine equation is very hard. But, for example, the equation a+b^{2}+c^{3}+d^{4}=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 nonnegative 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 nonnegative integer n each, where n < 10^{9}.
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
hide comments
Bhavik:
20131224 20:42:40
finally...:)) 

anurag garg:
20131224 15:14:31
very good question...


Mitch Schwartz:
20121209 14:13:25
As far as I can tell, current scoring system is: There are 5 input sets, and for each you get 2 points for AC, 0 points otherwise. Total score is sum of individual ones. 

Aditya Pande:
20121209 14:13:25
please define the scoring


Mitch Schwartz:
20121209 14:13:25
Thanks, although that introduces another (potential) issue  the problem is now scored as if it is a challenge problem, even though it is in classical section. It's some peculiarity of SPOJ system. See for example zukow's comment on NUMGUESS. (The reverse is also true  a problem in challenge section will count as classical if it has binary scoring set.) Last edit: 20121129 00:49:27 

Robert Gerbicz:
20121209 14:13:25
OK, changed the judge to maximize the score. 

Mitch Schwartz:
20121209 14:13:25
I probably also should have mentioned: For "accepted" solutions that fail some input sets, the time for the failed sets is not added to total time, so those submissions can seem fast when in fact they are wrong or too slow. Would it be possible to change to standard judge? Or I think changing the "limit" to 10 instead of 1 might have the same effect. And of course a rejudge would be appreciated. Last edit: 20121020 18:29:35 

Mitch Schwartz:
20121209 14:13:25
The constraints are VERY misleading. I spent a long time trying to find a faster algorithm, when my initial idea was fine.

Added by:  Robert Gerbicz 
Date:  20090907 
Time limit:  1s4s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 C++ 4.3.2 ERL JSRHINO NODEJS PERL6 SCALA 
Resource:  High School Programming League 