UOJ Logo

NOI.AC

#4. 爬楼梯

统计

题目描述

小时候我们都玩过爬楼梯的游戏:两人猜拳,赢了可向上爬一级,谁先到最高级则获胜。作为大学生,我们应该玩一个更有水平的游戏。 现在一个人要上n级楼梯,每一步可以选择上一级或者上两级,但是不能后退。求上这n级楼梯的方案数。

输入格式

第一行只有一个整数T(1<=T<=45),表示数据组数。 下面的T行每一行有一个整数n(1<=n<=45),表示有多少级楼梯。

输出格式

对于每一组数据输出一个整数s,表示方案数。

样例数据

input

4 
1 2 3 4

output

 1 2 3 5