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.

(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)