SPOJ.com - Problem SQUAREV1

SQUAREV1 - Revenge of the squares (variation)

no tags

Given a number N calculate the number R of different presentations of N in the form A*A+B*B with A and B being positive integers including zero. 1*1+2*2 and 2*2+1*1 are not different presentations. So for input 5 the output is 1.

Input

Fifty tests with one positive integer < 10^9.

Output

Print the illustrated above number R for each test.

Example

Input:
5
7
986244509

Output:
1
0
2

Submit solution!

hide comments

< Previous 1 2 Next >

	sonupmandal: 2016-05-20 12:20:35 Simple logic + 249 bytes :-)
	hodobox: 2015-09-22 11:07:26 Source limit isn't too low even for C++. I got 270 bytes without even thinking about source length optimization.
	Mitch Schwartz: 2014-07-16 22:05:46 81B in bash, with 0.00s as a bonus. :) Last edit: 2014-07-17 00:17:42
	anurag garg: 2013-12-18 12:15:30 good mathematics question... AC with 267 characters Last edit: 2013-12-18 12:15:56
	praveen123: 2012-06-18 02:02:04 You should think about C++ users they have to write using namespace std and for optimization also need cstdio ,,,, source size should be increased to 400
	aang™: 2012-06-13 16:35:14 problems with cin.eof() but why??
	Santiago Zubieta: 2011-06-06 21:32:04 Yes yes I know they are enough, in the end my solution measured about 270~ The thing is that I was very worried because I found out something to make it work (using a vector) but in the end after implementing the vector and its stuff I ended up with a bit more than 300 bits! But then I started removing other stuff and got under that limit :)
	HWK: 2011-06-06 11:47:54 @Santiago Zubieta: I thought 300 bytes are more than enough. You can read in the input description that there are 50 tests.
	Santiago Zubieta: 2011-06-06 01:53:09 This damn thing TLEs on me on Test #4 hahahaha :( EDIT: YES AFTER A LOT OF SUFFERING AND TRYS, ACC! At first I was getting a lot of TLEs because for some reason I thought I had to read a number of cases first, then I corrected it to EOF and started giving WA... Then I tried a lot of stuff, and my last solution came at a very suffering 306 characters so I tried everything possible to reduce it... and it worked! Last edit: 2011-06-06 04:13:04
	HWK: 2011-04-20 12:24:15 @Virgo: That's right.

Submit solution!

Added by:	HWK
Date:	2011-02-28
Time limit:	1s
Source limit:	300B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64