Problem Description

有一楼梯共 $M$ 级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第 $M$ 级，共有多少种走法？

Input

输入数据首先包含一个整数 $N$，表示测试实例的个数，然后是 $N$ 行数据，每行包含一个整数 $M(1 \leq M \leq 40)$,表示楼梯的级数。

Output

对于每个测试实例，请输出不同走法的数量

Samples

2
2
3

1
2