\includegraphics{https://static.e-olymp.com/content/13/1300e15b8d6877ff62e354354b0fdd71f41c58f4.jpg} ”\textit{Дорогой дядя Фёдор!} \textit{После того, как мама испугалась, что ты можешь заболеть какой-то нечеловеческой болезнью и забрала тебя в город, Шарик видимо все-таки чем-то заболел, ибо его поступки я уже иначе объяснить не могу, как последствиями постоянного общения с Хрюшей.} \textit{Суди сам: он сначала распилил шахматную доску на квадратики, потом на каждый квадратик наклеил изображение круглой скобки и, выдав определенное количество квадратиков, заставляет меня считать, сколько разных правильных скобочных последовательностей я смогу построить из имеющегося у меня числа квадратиков. При этом он еще и требует, чтобы я использовал все квадратики!} \textit{Я сначала обрадовался, так как помню, что из шахматной доски он не мог выпилить больше }\textbf{64}\textit{-х квадратиков. Но скоро понял, что я глубоко ошибался.} \textit{Дядя Фёдор, если тебе не трудно, напиши мне программу для подсчета этого количества, ибо из-за того, что Шарик задает мне свою непонятную задачу до }\textbf{20}\textit{ раз на день, у меня даже не остается времени ухаживать за моей любимой коровой.} \textit{Всегда твой верный друг -- кот Матроскин.}” Помогите дяде Фёдору написать программу для Матроскина, иначе тот может остаться без молока. \InputFile В первой строке задано число \textbf{n} -- количество заданий Шарика за день. В следующих \textbf{n} строках задано по одному числу \textbf{k} -- количество выданных в очередной раз Матроскину квадратиков с изображением скобок. Квадратики Матроскин может переворачивать, получая при этом как открывающую, так и закрывающую скобку. \OutputFile Вывести в \textbf{n} строках по одному числу -- ответ на соответствующее задание Шарика.