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 <= 20
1 <= n <= 20

Output

For each test case output the answer to the problem in the statement.

Example

Input:
3
2
3
4

Output:
2
0
5