SPOJ.com - Problem HS09EQ

HS09EQ - Diophantine equation

no tags

Sometimes solving a Diophantine equation is very hard. But, for example, the equation a+b²+c³+d⁴=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 < 10⁹.

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

Submit solution!

hide comments



	abhinav_jain02: 2019-06-13 16:21:08 Just brute force. Use sqrt() to avoid TLE.
	Bhavik: 2013-12-24 20:42:40 finally...:))
	anurag garg: 2013-12-24 15:14:31 very good question... pure logic...and maths
	Mitch Schwartz: 2012-12-09 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: 2012-12-09 14:13:25 please define the scoring score=? edit thanks mitch Last edit: 2012-12-01 18:38:45
	Mitch Schwartz: 2012-12-09 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: 2012-11-29 00:49:27
	Robert Gerbicz: 2012-12-09 14:13:25 OK, changed the judge to maximize the score.
	Mitch Schwartz: 2012-12-09 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: 2012-10-20 18:29:35
	Mitch Schwartz: 2012-12-09 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. 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

Submit solution!

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