## 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≤10^{15}.

### Output

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

### Example

Input:3 4 5 6Output: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) |