ADV04I1  Boards (Hard)
Super Board Games Inc. is a big company producing board games. A new game was invented within it which may become very popular. A board divided into square cells is required for this game. Left and lower borders of the board should be level and the height of columns of cells should not increase from left to right. Also the board must be entirely paveable with dominoes. After it was found out that the game is the most interesting when played on the board consisting of n cells, it has been decided to release as many versions of the game using different ncell boards as possible. Help the company count the number of different boards that can be released.
Input
The first line of input is number T  the amount of test cases. Each test is a single integer n  the number of cells.
Constraints
1 <= T <= 100
1 <= n <= 100
Output
For each test case output the answer to the problem in the statement.
Example
Input: 3 2 3 4 Output: 2 0 5
hide comments
Ashish Lavania:
20130502 04:44:37
for 3 why is ### or


Alex Anderson:
20130210 01:00:36
For the problem, we're using lots of 1xk rectangles, where k will change a lot. "Left and lower borders of the board should be level" means that you are placing your 1xk rectangles all on a flat surface, and they always touch the bottom:


Alex Anderson:
20121213 02:46:45
On the contrary, it is easy to understand what it is asking. Solving it is another matter. 

Ashish Lavania:
20121211 19:09:18
Boards(hard) : hard to understand?


.:: Pratik ::.:
20101215 10:20:58
Can the statement be explained more clearly?

Added by:  Spooky 
Date:  20101114 
Time limit:  1s 
Source limit:  1000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Advancement Autumn 2010, http://sevolymp.uuuq.com/, author: Alexey Shchepin 