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 ERL JS-RHINO NODEJS PERL6 SCALA
Resource:High School Programming League

hide comments
2019-06-13 16:21:08
Just brute force.
Use sqrt() to avoid TLE.
2013-12-24 20:42:40 Bhavik
finally...:))
2013-12-24 15:14:31 anurag garg
very good question...
pure logic...and maths
2012-12-09 14:13:25 Mitch Schwartz
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.
2012-12-09 14:13:25 Aditya Pande
please define the scoring
score=?

edit
thanks mitch

Last edit: 2012-12-01 18:38:45
2012-12-09 14:13:25 Mitch Schwartz
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: 2012-11-29 00:49:27
2012-12-09 14:13:25 Robert Gerbicz
OK, changed the judge to maximize the score.
2012-12-09 14:13:25 Mitch Schwartz
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: 2012-10-20 18:29:35
2012-12-09 14:13:25 Mitch Schwartz
The constraints are VERY misleading. I spent a long time trying to find a faster algorithm, when my initial idea was fine.

Also, there's an issue with judging: AC can be given even if some cases fail, as shown when clicking on "accepted". (I disqualified those submissions.)

Last edit: 2012-10-13 22:26:38
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.