3008 - 上台阶

楼梯有 n(1 ≤ n ≤ 30) 阶台阶,上楼时可以一步上1阶,也可以一步上2 ,也可以一步上3阶,计算共有多少种不同的走法。

输入

每一行包括一组测试数据,即为台阶数n(1 ≤ n ≤ 30),最后一行为0,表示测试结束

输出

每一行输出对应一行输入的结果,即为走法的数量

样例

输入

1
2
3
5
0

输出

1
2
4
13

来源

CIE等级考试

时间限制 1 秒
内存限制 64 MB
讨论 统计
上一题 下一题