Description

对于一个2行N列的走道。现在用1*2 , 2*2的砖去铺满。问有多少种不同的方式。

Input Format

第一行输入一个整数t，表示t组数据。

之后t行，每行一个正整数n（n<=25），表示走道列数

Output Format

输出每个n的铺砖方案数

2
8
12

171
2731

Source

信奥星OJ http://127.0.0.1