Hide
Catalan Numbers
Input
The first line of input consists of an integer $q$, where $1 \leq q \leq 1000$. Then follow $q$ lines, each containing an integer $x$ where $1\leq x\leq 5000$.
Output
Then for each query $x$, output a line containing $C_ x$, the $x$:th Catalan number.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 1 2 3 4 5 50 |
1 2 5 14 42 1978261657756160653623774456 |
