Super Board Games Inc. є гіганською компанією, яка займається виробництвом настільних ігор. Її співробітники винайшли нову гру, яка повинна стати дуже популярною. Для цієї гри потрібна ігрова дошка, поділена на квадратні клітинки. Лівий та нижній краї повинні бути рівними, і висота стовбців клітинок повинна незростати зліва праворуч. Також необхідно, щоб цю дошку можна було замостити пликами доміно \textbf{2}×\textbf{1}. Після того, як вияснили, що гра найбільш цікава, коли дошка складається з \textbf{n} клітинок, рада директорів компанії наказали випустити якомога більше варіантів гри, використовуючи різні \textbf{n}-кліткові дошки. Допоможіть порахувати, скільки усього модифікацій зможе випустити компанія. \includegraphics{https://static.e-olymp.com/content/69/69bf4b03e9d254b8f44e85de1316b9fb6b39b3c4.jpg} Рис. 1: Приклад двох дошок з \textbf{8} клітинок: допустимою (ліворуч) та яку не можна замостити плитками доміно (праворуч). \InputFile Перший рядок входу містить число \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{100}) --- кількість тестів. Наступні \textbf{T} рядків містять по одному цілому числу \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{100}). \OutputFile Для кожного \textbf{n} виведіть кількість можливих модифікацій гри.