Наслідки грипу в Простоквашино
”Дорогий дядько Федір!
Після того, як мама злякалась, що ти можеш захворіти якоюсь нелюдською хворобою і забрала тебе в місто, Шарик видно все-таки чимось захворів, бо його вчинки я вже інакше пояснити не можу, як наслідками постійного спілкування з Хрюшею.
Подумац сам: він спочатку розпилив шахову дошку на квадратики, потім на кожен квадратик наклеїв зображення круглої дужки і, давши певну кількість квадратиків, заставляє мене рахувати, скільки різних правильних послідовностей дужок я зможу побудувати з наявної у мене кількості квадратиків. При цьому він ще й вимагає, щоб я використовував всі квадратики!
Я спочатку зрадів, так як пом'ятаю, що з шахової дошки він не міг випилити більше 64-х квадратиків. Але швидко зрозумів, що я глибоко помилявся.
Дядько Федір, якщо тобі не важко, напиши мені програму для підрахунку цієї кількості, бо із-за того, що Шарик задає мені свою незрозумілу задачу до 20 разів на день, у мене навіть не залишається часу для догляду моєї любимої корови.
Завжди твій вірний друг – кіт Матроскін.”
Допоможіть дядьку Федору написати програму для Матроскіна, інакше той може залишитись без молока.
Вхідні дані
У першому рядку задано число n – кількість завдань Шарика за день. У наступних n рядках задано по одному числу k – кількість виданих у черговий раз Матроскіну квадратиків із зображенням дужок. Квадратики Матроскін може перевертати, отримуючи при цьому як відкриваючу, так і закриваючу дужку.
Вихідні дані
Вивести в n рядках по одному числу – відповідь на відповідне завдання Шарика.