题目描述

《贴图》

【贴图】递推法 小蓝的班级组织了一个《送祝福》活动。 首先给班级N位同学每人一张宽为1长为2的祝福贴，在祝福贴上写上每位同学的祝福语后，再将祝福贴贴到宽为2长为N的祝福墙上。 祝福贴贴到祝福墙上的方式可以竖着贴也可以横着贴，所贴的祝福贴紧挨着，不能有间隙，也就是每位同学必须要把祝福墙贴满。 小蓝班级有N位同学，每人手持一张1*2的祝福贴，刚好可以贴满 2 x N 的祝福墙。问贴满祝福墙共有多少种不同的贴法？

输入格式

输入的第一行包含一个正整数T（T<=20），表示一共有T组数据，接着是T行数据，每行包含一个正整数N（N<=30），表示墙面的大小是2行N列。

输出格式

输出一共有多少种铺设的方法，每组数据的输出占一行。

样例

输入样例 1

3
3
8
12

输出样例 1

3
34
233

输入样例 2

3
1
2
4

输出样例 2

1
2
5

输入样例 3

2
10
15

输出样例 3

89
987