Problem Description

有一个大小是 $2×n$ 的网格，现在需要用 $2$ 种规格的地砖铺满，地砖规格分别是 $2×1$ 和 $2×2$，请计算一共有多少种铺设的方法。

Input

输入的第一行包含一个正整数 $T(T≤20)$，表示一共有 $T$ 组数据，接着是 $T$ 行数据，每行包含一个正整数 $N(N≤30)$，表示网格的大小是 $2$ 行 $N$ 列。

Output

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

Samples

3
2
8
12

3
171
2731