找规律。。。

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

注：规定从一级到一级有0种走法。

输入

输入数据首先包含一个整数n(1<=n<=100)，表示测试实例的个数，然后是n行数据，每行包含一个整数m，（1<=m<=40),  表示楼梯的级数。

 

 

1. 1. 8阶台阶，小明从下向上走，若每次只能跨过1级或2级，他走上去共有多少种方法？ 
   2. 解：因为1阶台阶，1种走法； 
   3. 2阶台阶，有1+1、2，共2种走法； 
2. 3阶台阶，有1+1+1、1+2、2+1，共3种走法，即1+2=3； 
3. 4阶台阶，有1+1+1+1、1+1+2、1+2+1、2+1+1、2+2，共5种走法，即2+3=5； 
4. 5阶台阶，有1+1+1+1+1、1+1+1+2、1+1+2+1、1+2+1+1、2+1+1+1、1+2+2、2+1+2、2+2+1，共8种走法3+5=8； 
5. …… 
6. 所以6阶台阶，有5+8=13种；7阶台阶，有8+13=21种；8阶台阶，有13+21=34种； 
7. 结论：有n阶台阶，从下向上走，若每次只能跨过1级或2级，走法的规律为1，2，3，5，8，13，21……，即a1=1，a2=2，an=an-1+an-2 
8. 2.有10阶台阶，小明从下向上走，若每次只能跨过1级或2级或3级，他走上去共有多少种方法？ 
9.  
10. 解：因为1阶台阶，1种走法； 
11. 2阶台阶，有1+1、2，共2种走法； 
12. 3阶台阶，有1+1+1、1+2、2+1、3，共4种走法； 
13. 4阶台阶，有1+1+1+1、1+1+2、1+2+1、2+1+1、2+2、1+3、3+1，共7种走法，即1+2+4=7； 
14. 5阶台阶，有1+1+1+1+1、1+1+1+2、1+1+2+1、1+2+1+1、2+1+1+1、1+2+2、2+1+2、2+2+1、1+1+3、1+3+1、3+1+1、2+3、3+2，共13种走法2+4+7=13； 
15. …… 
16. 所以6阶台阶，有4+7+13=24种；7阶台阶，有7+13+24=44种；8阶台阶，有13+24+44=81种；9阶台阶，有24+44+81=149种；10阶台阶，有44+81+149=274种. 
17. 结论：有n阶台阶，从下向上走，若每次只能跨过1级或2级或3级，走法的规律为1，2，4，7，13，24，44，……，即a1=1，a2=2，a3=4，an=an-1+an-2+a