The consequences of influenza in Prostokvashino
”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 to 20 times 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
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.