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).