火车

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

        我们都知道,火车沿途会经过各种大大小小的站,火车在可能会跳过某些站不停靠,但是肯定不会连续跳过两站及以上。假设沿途一共会有m个站台(火车起初停靠在第一站),一共有多少种不同的停站方案?

Input

输入的第一行为一个整数 T (0 < T < 40),接下来为 T 组测试数据,每组只有一个整数 m (0 < m < 40),表示站台的数量。

Output

对于每组测试数据,输出只有一行为一个整数,表示可供选择的方案数。

Sample Input

2
2
3

Sample Output

1
2

Hint

样例说明:

m=2时,只有两个站,火车最初在1号站,所以只有一种方案。

m=3 时,有三个站,火车最初在1号站,它可以在2号站停靠,然后在三号站停靠。或者跳过2号站,到三号站停靠,所以共两种方案。

Source

qinchuan