An expression is termed as NICE, if the given bracket pairs are arranged in such a way such that for every left parentheses there is a right parenthesis and the matched pairs are well nested.

The following expressions gives the example for NICE expressions

() -- Nice
(()) - Nice
()() - Nice
())( - not Nice
)()( - not Nice

Kushagr wants to gift his girlfriend some expressions from the set of the bracket pairs. Since he wants to impress her, he would like the expressions to be nice.

Kushagr has n bracket pairs and he wants to find out the number of nice expressions he can make out of those bracket pairs. Example : For 3 bracket pairs he can form the following nice expressions ((())), ()(()), ()()(), (())(), (()()) so the answer is 5.

INPUT
You are given t test cases. Next t lines contains the number n .

OUTPUT
Print the maximum number of NICE expression for each test case in a new line

CONSTRAINTS
0 < t < 100000 0 < n < 100