”Дорогой дядя Фёдор!

   После того, как мама испугалась, что ты можешь заболеть какой-то нечеловеческой болезнью и забрала тебя в город, Шарик видимо все-таки чем-то заболел, ибо его поступки я уже иначе объяснить не могу, как последствиями постоянного общения с Хрюшей.

   Суди сам: он сначала распилил шахматную доску на квадратики, потом на каждый квадратик наклеил изображение круглой скобки и, выдав определенное количество квадратиков, заставляет меня считать, сколько разных правильных скобочных последовательностей я смогу построить из имеющегося у меня числа квадратиков. При этом он еще и требует, чтобы я использовал все квадратики! 

   Я сначала обрадовался, так как помню, что из шахматной доски  он не мог выпилить больше 64-х квадратиков. Но скоро понял, что я глубоко ошибался.

   Дядя Фёдор, если тебе не трудно, напиши мне программу для подсчета этого количества, ибо из-за того, что Шарик задает мне свою непонятную задачу до 20 раз на день, у меня даже не остается времени ухаживать за моей любимой коровой.

Всегда твой верный друг – кот Матроскин.”

   Помогите дяде Фёдору написать программу для Матроскина, иначе тот может остаться без молока.

   Входные данные

   В первой строке задано число n – количество заданий Шарика за день. В следующих n строках задано по одному числу k – количество выданных в очередной раз Матроскину квадратиков с изображением скобок.  Квадратики Матроскин может переворачивать, получая при этом как открывающую, так и закрывающую скобку.

   Выходные данные

   Вывести в n строках по одному числу – ответ на соответствующее задание Шарика.