游客 Signup | Login
中文 | En

2099 - 上台阶

通过次数

0

提交次数

0

Time Limit : 1 秒 Memory Limit : 128 MB

有一天,三萩实在太无聊了,竟然无聊到去数台阶了。有一个楼梯一共有m级,刚开始三萩在第一级,他就想,若每次只能跨上一级或者二级,要走上m级,共有多少种走法?

Input

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

Output

对于每个测试样例,请输出不同走法的数量。

Examples

Input Format

2
2
3

Output Format

1
2