As predicted by the great Gods, Little Arjit has got nothing to do this summer. (Are you surprised?) But, he's not one of those people to lose hope... not so easily. He decided to work hard this summer on the two things he wants the most, as of now: "Dual degree work", and "an internship!"

So, following the signs from the universe, he makes multiple chits like the one shown below, and folds them, and puts all of them in a jar.

Now, he follows a certain algorithm to complete his planned hard work in the 60 days of vacations, he's got.

• Let's say, little Arjit has c number of chits.
• Every day, he picks up a chit from the jar.
• If it's a normal, proper complete chit, he prefers selecting "dual degree" as his first choice.
• He finishes off the work selected from the chit; tears that portion, and puts back the remaining half of the chit, back in the jar.
• Let's say, if he picks a remaining half of some chit, he does that work - and so that chit's work is finished; and that chit is discarded.

Given the total number of chits made by Little Arjit, in how many ways can he finish of all his work?

Input format:
The first line contains an integer, t, denoting the number of test cases. The next t lines contain one integer, n, in every line, denoting the number of chits made by little Arjit.

Output format:
Print the number of ways he can empty the jar.

Constraints:
1 <= t <= 700
1 <= n <= 30

Obvious fact: For completing 30 chits, he'll be needing 30*2=60 days.