Let's Hit Our Head!

Kingdom LHOH is celebrating its annual carnival again!This time another crazy game is now on show.N*N piles of brick here lying on the ground in a straight line, and N brave fellows have attended.
First they should each choose a distinct piles brick to stand behind, forming a line parrelling to the brick, and facing the same side, watching at his piles of brick.
Then their captain can yelled out 3 commands, described below:
A "LEFT!" Every one should move so that he is behind the left piles of the original one.
B "RIGHT!" Every one should move so that he is behind the right piles of the original one.
C "HIT!" Every one should break all the piles of brick before him with only his head slamming them.

A little constraints are showed below:
In every step, when command A or B have been yelled out, no one should move outside, that is, for everyone after his moving, brick(even breaked up) is there before him,and when command C is to be yelled out, intact piles of brick must be there before every one, so that he cannot slamming brick that it already breaked up, and only that is fair to everyone.
Not until all piles of brick have been successfully breaked up with the brave fellows' heads, this game is successfully finished.
Now the question is,the crazy captain wants to know how many initial options are there,satisfying for each initial option he always chooses the first piles, other members choose their own distinct ones,and the game can be finished successfully at the same time?
We assume the other members except the captain cannot be told out.

First there's an integer T(T<=15000) indicating the scenary numbers.
Then there's T lines represented for the scenaries, with an integer N(1<=N<=10^12) in each line.

For each datus, you should output one integer in a line represented the answer for the scenary with N brave fellows and N*N piles of brick.And that's all.

10
1
2
3
4
8
16
6469693228
6469693229
6469693230
1024

1
2
2
6
20
70
84
14
8787513806478134
184756

BUPT

2012 Multi-University Training Contest 1