Description

软件实训基地阳台打算重新装修，而现在首要任务就是要对地面进行重新铺设。现在已知阳台的长度为n米，宽度为3米，并且有两种地板可以选用，规格分别是1米*1米 和 2米*2米;请你编写程序计算：若用这两种规格的地板铺设地面，共有多少种不同的方案可供选择？

Input

输入数据首先包含一个正整数T，表示包含T组测试用例，然后是T行数据，每行包含一个正整数n(1<=n<=30)，表示阳台的长度。

Output

对于每组测试数据，请输出铺设地砖的方案数目，每个输出占一行。

Sample Input

2
2
3

Sample Output

3
5

HINT

结果可能超出int范围！

Source

NBU OJ