Migrated from Lutece 768 进阶之路

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

自从来到清水河这种不毛之地，小明真是太寂寞了，在对妹纸们最后的一丝希望都破灭之后，他每天唯一的乐趣就是爬楼梯。

久而久之小明发现一个现象，由于他每次可以选择将步子迈小些或者迈大些，所以每迈一步既可以上升一阶或者两阶，因此对于同样一个楼梯，小明也有不同的爬法呢。

举个例子，对于一个 $5$ 阶的楼梯，小明可以选择下面的 $8$ 种方式：

(0, 1, 2, 3, 4, 5)
(0, 1, 2, 3, 5)
(0, 1, 2, 4, 5)
(0, 1, 3, 4, 5)
(0, 2, 3, 4, 5)
(0, 1, 3, 5)
(0, 2, 3, 5)
(0, 2, 4, 5)

推广开来，对于一个 $N$ 阶的楼梯，小明有多少种不同的方式呢？

Input

第一行是一个正整数 $T$，代表有 $T$ 组测试数据；

接下来是 $T$ 行输入，每行输入一个正整数 $N$ ($0 < N < 40$)，代表阶梯数量。

Output

对于每组测试数据，输出相应结果，每个结果单独占一行。

Samples

3
1
3
5

1
3
8

Resources

第四届”英才创协杯”ACM编程挑战赛