Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 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
杨少侠
© 2015 HUST ACMICPC TEAM. All Right Reserved.