爬楼梯

Time Limit: 1000 ms

Memory Limit: 65535 ms

[显示标签]

Description

似乎大家都有做电梯的习惯,现在为了锻炼身体,我们漂亮的贾琼姐姐提议大家天天走楼梯,另外一个方面,帆哥比较喜欢思考,他想知道到底有多少种方法能够走到楼顶。由于帆哥身体素质不够过关,他一次最多只能跨两个台阶,最少跨一个台阶。

Input

第一行给出测试样例的个数t(t<100) 接下来给出t行,每行给出楼梯的高度n(1<=n<=20)

Output

他一共有多少种不同的走法能够走到楼顶

Sample Input

2
2
19

Sample Output

2
6765

Hint

Source

Junhua Zhang

提交代码