INS14B  TRISQRS
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 Format:
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 Format
Output one line for each test case. Each line contains one integer which is the desired solution
Constraints:
1<=T<=1000
1<=N<=1000
Sample Input
2
1
2
Sample Output
0
2
hide comments
nadstratosfer:
20190317 05:43:14
Nice problem, read the description carefully  I've spent 1.5 hours figuring algorithms to compute sequences that, thankfully, this problem doesn't ask for. Last edit: 20190317 05:45:06 

Piyush Kumar:
20160622 12:28:44
This is an excellent question . Easy to code but a bit difficult to reach the solution by intuition. 

/* Nitin Jaiman */:
20150323 13:47:39
Finally AC. 

Vamsi Krishna Avula:
20141226 14:24:17
good problem! 

Surya kiran:
20140323 20:48:26
@Rishav : Yes


Rishav Goyal:
20140322 07:46:46
is it possible one side is 0.5 and other side is 4. ?? 
Added by:  Surya Kiran 
Date:  20140320 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Insomnia 2014 