PTC - Pythagorean Triple Counting

There are already some SPOJ problems related to Pythagorean triples. Here is another one: Given an integer n, calculate the number p(n) of Pythagorean triples with at least one cathetus of length n.

Input

Input starts with a positive integer t≤1000, the number of testcases.
Each of the following t lines contains a positive integer n≤1015.

Output

For every n print the value of p(n) in a single line.

Example

Input:
3
4
5
6

Output:
1
1
1

Explanation: The only Pythagorean triple that has a cathetus with length 4 is (3,4,5), so p(4)=1.

Note: If you find the time limit too strict, you may first try the tutorial version with identical test data, but increased time limit. I also recommend to solve problems WPC5A and CATHETEN first.


Added by:numerix
Date:2015-02-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:own problem (inspired by WPC5A)

hide comments
2018-05-23 03:17:45
@numerix,gut abend。Can I ask you some questions about triple。please email me: 2339572160@qq.com
2015-02-27 21:36:32 (Tjandra Satria Gunawan)(曾毅昆)
Be careful, test case is very strong! :-O
2015-02-21 08:44:22 [Lakshman]
@numerix This problem can be easily solve in less than .03 with one particular algorithm. However I have not used that one. I think number of test cases are still not enough.

Reply [numerix]: You are right according to the runtime, but I do not agree that it can be "easily done". Moreover it should be possible to solve the problem with slower languages with a good approach. According to my experiments and the submissions so far, I see no reason to change anything.

Last edit: 2015-02-21 10:54:10
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.