no tags 

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



Sample Input


Sample Output


hide comments
nadstratosfer: 2019-03-17 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: 2019-03-17 05:45:06
Piyush Kumar: 2016-06-22 12:28:44

This is an excellent question . Easy to code but a bit difficult to reach the solution by intuition.

/* Nitin Jaiman */: 2015-03-23 13:47:39

Finally AC.

Vamsi Krishna Avula: 2014-12-26 14:24:17

good problem!

Surya kiran: 2014-03-23 20:48:26

@Rishav : Yes
@NITIN : No more Test cases will be provided.

Rishav Goyal: 2014-03-22 07:46:46

is it possible one side is 0.5 and other side is 4. ??

Added by:Surya Kiran
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Insomnia 2014