Description

一个楼梯共有$M$级台阶，刚开始时我们站在第$1$级台阶上，若每次只可以走上一级或二级台阶，则要走上第$M$级台阶共有多少种走法？

Format

Input

第$1$行包含一个整数$N$ ，表示测试用例的个数。

然后是$N$行数据，每行都包含一个整数$M$$（$$1$$≤$$M$ $≤$$4$$0$$）$，表示楼梯的级数。

Output

对每个测试实例都输出不同走法的数量。

Samples

2
2
3

1
2

来源

HDU2041