Задачи
Последствия гриппа в Простоквашино
Последствия гриппа в Простоквашино
\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} строках по одному числу -- ответ на соответствующее задание Шарика.
Входные данные #1
3 2 3 4
Выходные данные #1
1 0 2