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