Дошки Hard#3185
Super Board Games Inc. — це велика компанія, яка виробляє настільні ігри. Її працівники винайшли нову гру, яка може стати дуже популярною. Для цієї гри потрібна дошка, поділена на квадратні клітинки. Лівий і нижній краї мають бути рівними, а висота стовпців клітинок не повинна зростати зліва направо. Крім того, має бути можливо покрити всю дошку доміно розміром 2 \times 1. Після визначення, що гра є найцікавішою на дошці, що складається з клітинок, рада директорів компанії вирішила випустити якнайбільше версій гри, використовуючи різні дошки на клітинок. Допоможіть компанії підрахувати кількість різних варіантів дощок, які можна випустити.
Рис. 1: Приклад двох дощок з клітинок: правильна (ліворуч) і така, яку неможливо повністю покрити доміно (праворуч).
У першому рядку задано одне ціле число (1 \leq T \leq 100) — кількість тестів. У наступних рядках міститься по одному цілому числу (1 \leq n \leq 100).
Для кожного виведіть кількість можливих варіантів гри.
Приклад 1