#NC14975. 方块与收纳盒

方块与收纳盒

题目描述

现在有一个大小为 n×1n\times1 的收纳盒,手里有无数个大小为 1×11\times1 和 2×12\times1 的小方块。需要用这些方块填满收纳盒,请问有多少种不同的方法?

输入格式

第一行是样例数T

第2到2+T-1行每行有一个整数n(n<=80),描述每个样例中的n。

输出格式

对于每个样例输出对应的方法数

提示

对于100%的数据,

0 < T < 80;

0 < n <= 80。

样例 1

3
1
2
4
1
2
5

样例说明

n=4,有五种方法

1:1 1 1 1

2:2 1 1

3:1 2 1

4:1 1 2

5:2 2

来源

牛客原题