\includegraphics{https://static.e-olymp.com/content/13/1300e15b8d6877ff62e354354b0fdd71f41c58f4.jpg} ”\textit{Dear Uncle Fyodor!} \textit{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.} \textit{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.} \textit{He also demands that I used all the squares!} \textit{At first I was glad, because I remember that from the chessboard, he could not cut it out more than }\textit{\textbf{64}}\textit{ squares.} \textit{But soon realized that I was profoundly mistaken.} \textit{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} \textbf{20} \textit{times a day, I do not even have time to care for my beloved cow.} \textit{Always your faithful friend - a cat Matroskin.}” Help Uncle Fyodor to write a program for Matroskin, otherwise he can be remained without milk. \InputFile The first line contains the number of jobs \textbf{n} for Sharik per day. Each of the next \textbf{n} lines contains the number \textbf{k} of squares given to Matroskin with the image of brackets. Matroskin can rotate squares receiving both opening and closing parenthesis. \textbf{Ouput} Print \textbf{n} numbers, one per line, the answers to the Sharik's task.