CATHETEN - Shared cathetus (easy)

no tags 

For any integer n, we define F(n) as the number of ways in which n can be the cathetus (leg) of a Pythagorean triangle.
For example, there is exactly four Pythagorean triangles with 15 as a length for a cathetus.

catheten

(8 15 17), (15 20 25), (15 36 39), (15 112 113)

Thus F(15) = 4.

Input

The first line of input contains an integer T, the number of test cases.

Each of the next T lines contains a single integer n.

Output

For each test case, print F(n) on a single line.

Example

Input:
3
5
10
15

Output:
1
1
4

Constraints

0 < T < 10^5
0 < n < 10^9

For your information, my C code ran in 0.08s, whereas my python3 one ran in 0.90s. (Edit 2017-02-11, after compiler changes)


hide comments
Ikhaduri: 2013-04-26 12:07:21

Why sigsegv?
--ans--> Sorry I will not help you on that point. I just can say that on my own hardware, your code gives SIGSEV too. I recommend (if not yet done) to build some random input file that correspond to given constraints, and debug... Good luck.
ans--> Such a silly mistake.. :D

Last edit: 2013-04-30 07:55:16
(Tjandra Satria Gunawan)(曾毅昆): 2013-04-20 16:23:42

Pascal and C is different language!
--ans--> Yes, but choose only one Pascal, and one C-like in this case, please. After that, I'll not merge rank list. ;-)
Edit(Tjandra): I agree that C and C++ is similar in syntax and speed, but gpc (GNU pascal) and fpc (free pascal) is complete different compiler and source, like python 2 and python 3, some syntax is different, also gpc is ~3x slower than fpc. why you consider it same? Is that so you should consider that python 2 and python 3 is same too.. I hope you understand my explanation :-)
--ans--> ~
Edit(Tjandra): thanks :-)

Last edit: 2013-04-20 16:39:10
(Tjandra Satria Gunawan)(曾毅昆): 2013-04-20 16:23:42

NZEC bug..
--ans--> It's not a real NZEC, it's a TLE... You have to improve your algo* to get AC in Python. ;-)
(* Although you got 0.09s in C where I got 0.10s, our codes are quite different, in Python it makes a difference).
Edit(Tjandra): yes, I should learn more about python to speedup, that's my best for now...

Last edit: 2013-04-20 15:42:37

Added by:Francky
Date:2013-04-19
Time limit:1.899s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Old problem