In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects. They are named after the Belgian mathematician Eugène Charles Catalan (1814–1894).

An alternative expression for C_n is

The Catalan numbers satisfy the recurrence relation

moreover,

Input Format:
The first line of input consists of an integer Q . Then follow Q lines, each containing an integer X.

Output Format:
For each query X, output a line containing C_X, the X^th Catalan number.

Constraints:
1 ≤ Q ≤ 1000
1 ≤ X ≤ 5000