ADV04I1 - Boards (Hard)

no tags 

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 n-cell 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: 2013-05-02 04:44:37

for 3 why is ### or
#
#
# not possible?....plz define paveable!
--ans(francky)--> paveable is meant with 1×2 rectangles.
Re: thanks!!
btw,one of the toughest problems I ever came across!

Last edit: 2013-05-14 00:12:13
Alex Anderson: 2013-02-10 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:
Ex of a board with N = 10 cells.
##
###
#####
"height of columns of cells should not increase from left to right" means that the height should be equal or lesser when you go to the right. Here is goes 3 3 2 1 1.
" paveable with dominoes." means that if you looked at your board, you should be able to cover it with dominoes:

Ex: N = 6, can pave
##
##
##
Ex: N = 6, can't pave
#
##
###

So it is asking how many arrangements are there such that it uses N cells, the heights do not increase from left to right, and you can pave it with dominoes.

Alex Anderson: 2012-12-13 02:46:45

On the contrary, it is easy to understand what it is asking. Solving it is another matter.

Ashish Lavania: 2012-12-11 19:09:18

Boards(hard) : hard to understand?
@Alex Please help me then in understanding it

Last edit: 2012-12-20 15:39:03
.:: Pratik ::.: 2010-12-15 10:20:58

Can the statement be explained more clearly?
What is "paveable"?
Can there be explanation for the sample IO?


Added by:Spooky
Date:2010-11-14
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