e-olymp
Задачі

Наслідки грипу в Простоквашино

Наслідки грипу в Простоквашино

prb399Дорогий дядько Федір!

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

Подумац сам: він спочатку розпилив шахову дошку на квадратики, потім на кожен квадратик наклеїв зображення круглої дужки і, давши певну кількість квадратиків, заставляє мене рахувати, скільки різних правильних послідовностей дужок я зможу побудувати з наявної у мене кількості квадратиків. При цьому він ще й вимагає, щоб я використовував всі квадратики!

Я спочатку зрадів, так як пом`ятаю, що з шахової дошки він не міг випилити більше 64-х квадратиків. Але швидко зрозумів, що я глибоко помилявся.

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

Завжди твій вірний друг – кіт Матроскін.

Допоможіть дядьку Федору написати програму для Матроскіна, інакше той може залишитись без молока.

Вхідні дані

У першому рядку задано число n – кількість завдань Шарика за день. У наступних n рядках задано по одному числу k – кількість виданих у черговий раз Матроскіну квадратиків із зображенням дужок. Квадратики Матроскін може перевертати, отримуючи при цьому як відкриваючу, так і закриваючу дужку.

Вихідні дані

Вивести в n рядках по одному числу – відповідь на відповідне завдання Шарика.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3
2
3
4
Вихідні дані #1
1
0
2