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{20}) --- количество тестов. Следующие \textbf{T} строк содержат по одному целому числу \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{20}). \OutputFile Для каждого \textbf{n} выведите количество возможных модификаций игры.