It's September now, We are about to have Pantheon this month. This time the incharge of panthoen(Core) wants to call Sonu Nigam. Sonu nigam is a wonderful person. He accepted the invitation from the Core, but demanded a favour in return.
He asked for a lighted carpet to be laid for him to walk upto stage.

Everyone has heard about the Red carpet, But no one has ever heard about the Lighted carpet. So let me first explain what a lighted carpet is:
Lighted carpet is same as the red carpet, with an only difference that instead of being red, its like a dance floor. Now, Everyone knows how a dance floor looks like its a rectangular structure, with square tiles of equal sizes placed on it and lights glowing beneath each tile in a random fashion. Core wants to save money in every possible way they could, and at the same time also wants to fulfill the demands of their guest. so they came up with a plan, instead of using one bulb per tile, they started using 1 bulb per 2 tiles, so as to use half the bulbs required, and save electricity consumption.
just for curiosity, These people wanted to know how many ways they could arrange these bulbs. In other words how many ways, they could group(on a 2D carpet) two tiles together.
Could you try helping them with it.

Given the lighted carpet is 3 units wide and N units long (Assume N to be even).
Each tile is 1 unit wide and 1 unit long.
Each bulb is responsible for lightning exactly 2 tiles.
No tiles should be lighted by more than 1 bulb, and no tiles should be left unlighted.

INPUT:
first line contains number of test cases T
Each of the T lines below it contains length of the carpet(N)

OUTPUT:
For each test case print number of possible ways in a new line.

CONSTRAINTS:
0 < T < 31
0 < N < 61

SAMPLE INPUT:
2
2
4

SAMPLE OUTPUT:
3
11

Problem Setter : Sumit Kumar

Languages: Brain,C,C++,Java,Pascal,Perl,PHP,Python,Ruby,Text

Time Limit: 1 Second(s)
Score: 0 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0