After coming back from the ACM World Finals '13, Digo decided to celebrate his performance by watching a lot of action movies. Sitting in front of his laptop for days watching his favourite stars battle it out, Digo suddenly got inspired to join the CIA. Digo is a serious man, and vowed that he'd be inducted in the CIA force by the end of the year. And mind you, he takes his vows very seriously!

After sweating it out in the field for months, it's finally time for his interview. The interviewer believes that mental agility is as important as physical fitness and decides to test our hero with a mathematical puzzle.

The interviewer hands Digo a square of side N and asks him to partition the square into a number of right angled triangles, each having an equal integral area. Two sides of the triangle should be parallel to the two sides of the square. Being an ACM World Finalist, Digo solves the question in a split second. Impressed, the interviewer decided to test him with a harder question. He asks Digo to tell him the number of such partitions possible. All partitions having the same number of right triangles are considered the same.

Input

First line will contain T, the number of test cases. Next T lines will contain a single integer each N, denoting the size of the square.

Output

Output one line for each test case. Each line containing one integer which is the desired solution.

Constraints

1 <= T <= 1000
1 <= N <= 1000

Example

Input:
2
1
2

Output
0
2