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

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

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

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

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

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

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

   Вхідні дані

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

   Вихідні дані

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