1207 - PB

Time Limit: 1s Memory Limit: 128MB

Submissions: 196 Solved: 125
Description
PB is the nickname of a student in Hust.As all we know,PB is good at math.One day,when he is walking with his classmates,he told others a problem.He wonder whether they can find the solution of the problem. The question is as follows: Give you a big box of size 1*N,Then give you N 1*1 boxes and N 1*2 boxes,can you calculate how many kinds of method you can use the little boxes to fill the big box. Be careful: The next two kinds are not the same.
Input
First Line: One number indicate the number of test cases CAS.(1<=CAS<=1000) Then Each case contain one line with one number N(0<=N<=40).
Output
Just print one number in a line for each case.
Sample Input
5

34

24

30

35

2

Sample Output
9227465

75025

1346269

14930352

2

Hint
Hope everyone can pass this problem!
Source
杨少侠