題目描述

有一張大小是 2 * n 的方格紙，你想用2種規格的貼紙將它貼滿，貼紙的規格分別是 2 * 1 和 2 * 2，請計算一共有多少種貼滿的方法。

輸入格式

輸入的第一行包含一個正整數T（T<=20），表示一共有T組資料，接著是T行資料，每行包含一個正整數N（N<=30），表示方格紙的大小是2行N列。

輸出格式

輸出一共有多少種貼滿的方法，每組資料的輸出占一行。

Samples

3
2
8
12

3
171
2731

原始資料

• Zero1 題號：b127
• Hydro 題號：Z1127
• Locale：zh_CN
• Display：practice