1565: 盖瓦
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：64
题目描述
假设有一些相似的多米诺骨牌，每张牌正好可以覆盖棋盘上两个相邻方格。我们将 n 张多米诺骨牌摆放在 2 × n 棋盘上，使得没有任何两张牌重叠，且在每张牌覆盖两个方格的条件下覆盖棋盘上所有方格。我们把这样的摆放称为棋盘的多米诺骨牌的完美覆盖或者盖瓦。
设 f(n) 为 2 × n 棋盘的多米诺骨牌盖瓦的方案数。
设 f(n) 为 2 × n 棋盘的多米诺骨牌盖瓦的方案数。
输入
第一行输入一个正整数 T（T <= 20） 表示样例个数
接下来 T 行每行输入一个正整数 n （n <= 20）
接下来 T 行每行输入一个正整数 n （n <= 20）
输出
每行输出对应的 f(n)
样例输入 复制
3
2
4
7样例输出 复制
2
5
21提示
试着列出前几项