题目描述

树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数。

例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级，也可以第一次走两级，第二次走一级，一共3种方法。

输入

第一行一个正整数M，表示有M次询问。

接下来一行M个用空格隔开的正整数，代表每次询问的楼梯级数。

输出

输出M行，每行数字代表该次询问的楼梯走法。

样例

3
5 8 10

8
34
89

Others

对于 80%的测试点：M<10,楼梯级数<=30

对于100%的测试点：M<=1000,楼梯级数<=42