题目描述

有一块 $2 \times N$ 的网格地板，现在需要用 $2$ 种规格的地砖铺满，地砖的规格分别是 $2 \times 1$ 和 $2 \times 2$，请问一共有多少种铺设方法？

输入格式

第一行包含一个正整数 $T$，表示一共有 $T$ 组测试数据。
接下来 $T$ 行，每行包含一个正整数 $N$，表示网格的大小是 $2$ 行 $N$ 列。

输出格式

输出共 $T$ 行，每行一个整数，表示对应 $N$ 的铺设方法总数。

样例

3
2
8
12

3
171
2731

数据范围

• $T \le 20$
• $N \le 30$