Boards (Hard)#3185
Super Board Games Inc. is a large company that produces board games. Its employees have invented a new game, which may become very popular. This game requires a board divided into square cells. The left and lower edges must be level, and the height of the columns of cells must not increase from left to right. In addition, it must be possible to tile the entire board with 2 \times 1 dominoes. After determining that the game is most interesting when played on a board consisting of cells, the company's board of directors decided to release as many versions of the game as possible using different -cell boards. Help the company calculate the number of different board variations that can be released.
Fig. 1: Example of two boards with cells: a valid one (left) and one that cannot be tiled with dominoes (right).
The first line contains an integer (1 \leq T \leq 100) — the number of test cases. The next lines each contain a single integer (1 \leq n \leq 100).
For each , output the number of possible versions of the game.
Example 1