In the Galactical Wars happens the great event of designing a structure to honour the current generation of participants. (It is another matter that inevitably the monument is destroyed at the end of the Galactical Wars).

The organizers this year do not believe that this is a good event, and have reduced the event to building a right structure: a right-angled triangle that represents the geometry of the universe. Further they have given a specific Odd Integer n, which they want one of the Shorter sides of the triangle to be.

The organizers in the galaxy H2 are infuriated with this high-handedness. To demonstrate their prowess in this event, they have decided to build all possible right structures. Calculate how many different right structures they can possibly build.

Input

First line contains a single integer T, denoting the number of Test Cases.

T lines follow, each containing an odd integer ’n’ denoting the given size of a side.

Output

T lines, each containing a single integer denoting the number of ways to form a right angled triangle with one of the smaller sides as ’n’.

Constraints

1 <= T <= 10

1 <= n <= 10^12

n is odd.

Example

Input:
1
3

Output:
1

Explanation

There exists only 1 right angled triangle with sides 3, 4, 5.