11310 - Delivery Debacle

Wolfgang Puck有兩個特別的習慣：

• 他只切兩種形狀的蛋糕，單位面積為一的正方形，與單位面積為三的L形。
• 他只將蛋糕放入特定大小的盒子內，盒子的的長度不固定，但是寬度一定是2。

他想知道將蛋糕放入盒子內共有幾種擺放方式。

左圖為兩種形狀的蛋糕。右圖為將蛋糕擺放進2x6的盒子內的其中一種方式。

 

將蛋糕放入2x2盒子內的所有可能方式。

Input

輸入一開始會有一個整數 t 表示測試資料的組數，接下來有 t 個整數 n (1 <= n <= 40)表示盒子的長度。

Output

針對每組測試資料，輸出將蛋糕擺放進2 x n大小的盒子內的所有可能方式總數，輸出值一定會小於10^18。

Sample Input

2

1

2

Output for the Sample Input

1

5

---

原文出處