We all know that computer is a dumb machine. Behind the illusion of this entire magical works, computability and amazing things there are very few things it actually does. Do you know that computers can only understand 0 and 1? How dumb is that!

And behind all of its complex calculations it only does two things, addition and subtraction. All other calculations are done on the top of these basic operations. I hope you know that already. Whatever it does behind the scene is not actually matter to us as a user. We find it amazing that it can do many things, sometimes beyond imagination of regular users.

Now the thing that is related to this problem is one of the computer’s common operations, multiplication. Computer can multiply two things at a time. So if we have an operation like this-

a*b*c

It can be done in any of the two ways,

i)                    ((a*b)*c)

ii)                  (a*(b*c))

The operation is non-associative and the order of the elements (a,b,c,d) can’t be changed.

Now if I ask you do this multiplication, I know it would be a silly task to you and you won’t like that (because you are a good programmer). So in this problem I am asking you to calculate the number of ways to multiply n terms. Which is for the given example is 2 for n=3 terms (a,b,c).

Input will have number of test case T as first input following T test cases with each line having n(0<n<=20). You have to find the number of ways to multiplying n terms as described above. Answer will fit in 32-bit integer.

Sample Input:

2
3
4

Sample output:

2
5

Explanation:

First input is explained in the description.

For the second input, number of ways to multiply 4 terms a,b,c,d would be-

1)     ((a*b)(c*d))

2)     (((a*b)*c)*d)

3)     ((a*(b*c))*d)

4)     (a*((b*c)*d))

5)     (a*(b*(c*d)))

Authored By: Alavola