\includegraphics{https://static.e-olymp.com/content/13/1300e15b8d6877ff62e354354b0fdd71f41c58f4.jpg} ”\textit{Дорогий дядько Федір!} \textit{Після того, як мама злякалась, що ти можеш захворіти якоюсь нелюдською хворобою і забрала тебе в місто, Шарик видно все-таки чимось захворів, бо його вчинки я вже інакше пояснити не можу, як наслідками постійного спілкування з Хрюшею.} \textit{Подумац сам: він спочатку розпилив шахову дошку на квадратики, потім на кожен квадратик наклеїв зображення круглої дужки і, давши певну кількість квадратиків, заставляє мене рахувати, скільки різних правильних послідовностей дужок я зможу побудувати з наявної у мене кількості квадратиків. При цьому він ще й вимагає, щоб я використовував всі квадратики!} \textit{Я спочатку зрадів, так як пом`ятаю, що з шахової дошки він не міг випилити більше }\textbf{64}\textit{-х квадратиків. Але швидко зрозумів, що я глибоко помилявся.} \textit{Дядько Федір, якщо тобі не важко, напиши мені програму для підрахунку цієї кількості, бо із-за того, що Шарик задає мені свою незрозумілу задачу до }\textbf{20}\textit{ разів на день, у мене навіть не залишається часу для догляду моєї любимої корови.} \textit{Завжди твій вірний друг -- кіт Матроскін.}” Допоможіть дядьку Федору написати програму для Матроскіна, інакше той може залишитись без молока. \InputFile У першому рядку задано число \textbf{n} -- кількість завдань Шарика за день. У наступних \textbf{n} рядках задано по одному числу \textbf{k} -- кількість виданих у черговий раз Матроскіну квадратиків із зображенням дужок. Квадратики Матроскін може перевертати, отримуючи при цьому як відкриваючу, так і закриваючу дужку. \OutputFile Вивести в \textbf{n} рядках по одному числу -- відповідь на відповідне завдання Шарика.