2013年7月13日 星期六

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