题目描述

有一块大小是 $2 * n$ 的墙面，现在需要用 $2$ 种规格的瓷砖铺满，瓷砖规格分别是 $2 * 1$ 和 $2 * 2$，请计算一共有多少种铺设的方法。

输入格式

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

输出格式

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

样例

3
2
8
12

3
171
2731

数据的规模与约定

$T\in(0,20]$

$N\in(0,30]$