Wolfgang Puck 有兩個很特別的習慣：
- 他只做兩種形狀的蛋糕。一種是面積為一單位的方形，另一種是面積為三單位的 L 形。
- 他只用特定尺寸的盒子來裝蛋糕。這些盒子的寛度都是二單位，但各種不同長度都有。
有一天，Wolfgang 想知道有幾種不同的方式可以把蛋糕裝滿一個特定尺寸的盒子。你能幫他嗎？
左圖為蛋糕的尺寸，右圖為裝滿長度 6 的盒子的一種方法。
裝滿長度為 2 的盒子的 5 種方法。
Input
輸入的開始有一個 $t$，表示有幾個不同長度的盒子。接下來的 $t$ 行每行有一個整數 $n$ ($1\leq{n}\leq{40}$)
Output
相對於每個 $n$ 輸出一行，該行中的數字為有幾種方法可以用上述的蛋糕裝滿一個 $2\times{n}$ 的盒子。輸出的數字保證小於 $10^{18}$。
Sample Input
2
1
2
Output for the Sample Input
1
5