走楼梯

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

小虎发现走楼梯的时候一次上一个台阶比较惬意,一次上两个台阶比较高效,一次上三个台阶就很累人。
小虎是一个即注重质量又注重高效的人,于是他就在上楼梯的时候每步就只跨上一个台阶或两个台阶,
现在小虎想知道他这样上n阶的楼梯一共有多少种走法,但是他又不想亲身经历,只好求助于会编程的你,帮他解决这个问题了。
 

Input

第一行是T,表示接下来有T组输入,每组输入一个N(2 <= N <= 1000)

Output

对应每组输入输出一共有多少种走法。

Sample Input

3
10
9
22

Sample Output

89
55
28657

Hint

 

Source