PTCLONG - Pythagorean Triple Counting (LTL)

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 your solution is fast enough, you may try the classical version with identical test data, but stricter time limit. I also recommend to solve problems WPC5A and CATHETEN first.


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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.