1224 - Tile Code

韓國松波區現在著手進行一個腳踏車系統規劃，名為 "綠色松波"。在今年年底，市民和遊客都可以在整座城市中使用自行車，近期決定在自行車上數字標記，以方便管理。自行車將會在城市交通系統的管理控制下。

數字標記為一條長度為 n 的磚瓦條碼，每個將由 1 x 2, 2 x 1, 2 x 2 的磚瓦所構成，而條碼將會是個 2 x n 的長方形板子，每個方格只會由一個磚瓦覆蓋，長方形板子可以畫分成 2n 個 1 x 1 的方格。當然兩個磚瓦不會有重疊的部分，如下圖一是個 2 x 5 的 n = 5 長方形板，而圖二則是其中一種擺放方式，雖然條碼總是由左而右去讀，但是卻沒有上下之分，因此圖二和圖三是屬於同一種條碼。

給一個正整數 n，專案負責人 Dr. Yang 想要知道當長度為 n 時，有多少磚瓦條碼可以被使用，限定放入上述三種磚瓦於 2 x n 的長方形板。

Input 

第一行會有會有一個整數 T ，表示接下來有多少組測資。
每組測資會有一個正整數 n，3  <= n <= 30。

Output 

對於每組測資，輸出方法數。

Sample Input 

2 
3 
4

Sample Output 

3 
8