Boards (Easy)#3184
Super Board Games Inc. is a major company that produces board games. They have invented a new game that is expected to become very popular. This game requires a board divided into square cells. The left and lower edges of the board must be straight (level), and the height of the columns of cells must not increase from left to right. Additionally, the board must be completely tileable with domino tiles of size 2 \times 1.
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 all different -cell boards. Help count how many different board modifications can be released by the company.
Figure 1: Example of two boards consisting of cells: a valid one (left) that can be tiled with dominoes, and an invalid one (right) that cannot.
The first line contains (1 \leq T \leq 20), the number of test cases. Each of the following lines contains a single integer (1 \leq n \leq 20).
For each , output the number of possible modifications of the game.
Example 1