Доски Easy
Super Board Games Inc. является крупнейшей компанией, занимающейся производством настольных игр. Её сотрудники изобрели новую игру, которая должна стать очень популярной. Для этой игры требуется игровая доска, поделённая на квадратные клетки. Левый и нижний края должны быть ровными, и высота столбцов клеток должна невозрастать слева направо. Также необходимо, чтобы эту доску можно было замостить плашками домино 2×1. После того, как выяснили, что игра наиболее интересна, когда доска состоит из n клеток, совет директоров компании приказал выпустить как можно больше вариантов игры, используя различные n-клеточные доски. Помогите посчитать, сколько всего модификаций сможет выпустить компания.
Рис. 1: Пример двух досок из 8 клеток: допустимой (слева) и которую нельзя замостить плашками домино (справа).
Входные данные
Первая строка входа содержит число T (1 ≤ T ≤ 20) — количество тестов. Следующие T строк содержат по одному целому числу n (1 ≤ n ≤ 20).
Выходные данные
Для каждого n выведите количество возможных модификаций игры.