”Дорогой дядя Фёдор!”Дорогой дядя Фёдор!
После того, как мама испугалась, что ты можешь заболеть какой-то нечеловеческой болезнью и забрала тебя в город, Шарик видимо все-таки чем-то заболел, ибо его поступки я уже иначе объяснить не могу, как последствиями постоянного общения с Хрюшей.
Суди сам: он сначала распилил шахматную доску на квадратики, потом на каждый квадратик наклеил изображение круглой скобки и, выдав определенное количество квадратиков, заставляет меня считать, сколько разных правильных скобочных последовательностей я смогу построить из имеющегося у меня числа квадратиков. При этом он еще и требует, чтобы я использовал все квадратики!
Я сначала обрадовался, так как помню, что из шахматной доски он не мог выпилить больше 64-х квадратиков. Но скоро понял, что я глубоко ошибался.
Дядя Фёдор, если тебе не трудно, напиши мне программу для подсчета этого количества, ибо из-за того, что Шарик задает мне свою непонятную задачу до 20 раз на день, у меня даже не остается времени ухаживать за моей любимой коровой.
Всегда твой верный друг – кот Матроскин.”
Помогите дяде Фёдору написать программу для Матроскина, иначе тот может остаться без молока.
Входные данные
В первой строке задано число n – количество заданий Шарика за день. В следующих n строках задано по одному числу k – количество выданных в очередной раз Матроскину квадратиков с изображением скобок. Квадратики Матроскин может переворачивать, получая при этом как открывающую, так и закрывающую скобку.
Выходные данные
Вывести в n строках по одному числу – ответ на соответствующее задание Шарика.
Пример входных данных32 3 4 |
Пример выходных данных10 2 |