eolymp
bolt
Try our new interface for solving problems
Problems

The consequences of influenza in Prostokvashino

The consequences of influenza in Prostokvashino

Time limit 1 second
Memory limit 128 MiB

Dear Uncle Fyodor!

After the mother was afraid that you can get sick of some superhuman disease and take you to the city, Ball seems still somewhat ill, for his actions, I have another I can not explain how the effects of permanent communication with Piggy.

Judge for yourself: it will first cut the squares on a chessboard, then on each square pasted picture parentheses and by giving a certain number of squares, leads me to believe how many different correct bracket sequences can I build from my possession in the number of squares.He also demands that I used all the squares!

At first I was glad, because I remember that from the chessboard, he could not cut it out more than 64 squares.But soon realized that I was profoundly mistaken.

Uncle Fyodor, if you're not hard to write me a program to calculate this quantity, because of the fact that the ball gives me his incomprehensible task up to20times a day, I do not even have time to care for my beloved cow.

Always your faithful friend - a cat Matroskin.

Help Uncle Fyodor to write a program for Matroskin, otherwise he can be remained without milk.

Input data

The first line contains the number of jobs n for Sharik per day. Each of the next n lines contains the number k of squares given to Matroskin with the image of brackets. Matroskin can rotate squares receiving both opening and closing parenthesis.

Ouput

Print n numbers, one per line, the answers to the Sharik's task.

Examples

Input example #1
3
2
3
4
Output example #1
1
0
2
Author Анатолий Присяжнюк