Migrated from Lutece 589 lentty's diary

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Lentty bought a beautiful diary one day and she keeps a good habit of writing diary everyday.

The diary has $N$ pages.On the first day,she chooses a random page and finishes half of it.

On subsequent days, she chooses a random page(which can be either a whole unwritten page or half unwritten page).

If it is a half unwritten page ,she will finish it.If it is a whole unwritten page, she only finishes half of it.

In how many ways can she finish her diary? We represent the sequence of pages in the course of $2N$ days as a string, where the $i_{th}$ character is $W$ if a whole unwritten page was chosen on the $i_{th}$ day, and $H$ if a half unwritten page was chosen ($0 \leq i < 2N$). How many different valid strings are there that finish the diary?

Input

The first line of the input is an integer $T$ which stands for the number of test cases.

Each line of the following is a test case and contains a positive integer number $N$($N\leq 30$), the number of pages of the diary.

Output

For each problem instance, the output will be a single number, the number of different ways the diary can be finished.

Samples

5
1
2
3
5
30

1
2
5
42
3814986502092304

Resources

Sichuan University Programming Contest