题目描述

在 $2 \times n$ 的长方形方格中，用若干 $1 \times 2$ 的骨牌铺满方格。

输入 $n$ ，计算铺放方案的总数。

例如 $n==3$ 时，对于 $2 \times 3$ 的长方形方格，骨牌的铺放方案数为 $3$，具体铺放方案如下：

输入格式

第 $1$ 行是一个正整数 $N$；

接下来有 $N$ 行，每行是一个非负整数 $n_i$，表示该组要计算的是 $2 \times n_i$ 的长方形方格的铺放方案数。

输出格式

$N$ 行，每行一个整数，就是对应输入的 $N$ 个长方形方格的铺放方案数。

输入输出样例

5
10
20
30
40
50

89
10946
1346269
165580141
20365011074

说明/提示

👀️ 对于$100\%$ 的数据，$1 \leq N \leq 10000，0 \leq n_i \leq 5000$。