Покоління триблів
Трібли — це милі, пухнасті, лагідні створіння з ненаситним апетитом і швидкістю розмноження, що може конкурувати з будь-яким складним організмом у галактиці (трібли народжуються вагітними!). Після того, як їх було введено на "Ентерпрайз" та його екіпаж, швидко стало зрозуміло, якою неприємністю можуть бути трібли. За дуже короткий час трібли були всюди на кораблі.
На щастя для "Ентерпрайза", інженер Скотт зміг транспортувати їх на сусідній клінгонський корабель. Клінгони не знали про проблеми, які можуть спричинити трібли, і привезли їх у клінгонський простір, де трібли поширилися, як сарана, і знищили екосистеми планет по всій Клінгонській Імперії.
Члени Об'єднаної Федерації Планет (Федерація) вважали це надзвичайно кумедним і використовували обчислення розмноження тріблів як академічну вправу для студентів першого курсу в своїй академії.
Наступна послідовність чисел представляє, як розмножуються трібли. Перше число представляє покоління 0, друге покоління 1, і так далі.
1, 1, 2, 4, 8, 15, 29, 56
Наступна рекурентна формула може бути використана для представлення вищезгаданої послідовності, де n представляє номер покоління:
n < 2 : 1
n = 2 : 2
n = 3 : 4
n > 3 : gen(n-1) + gen(n-2) + gen(n-3) + gen(n-4)
Ті, хто в академії знає щось про стару історію Землі, жартома назвали цю рекурентну формулу 'Тріббоначчі'.
Ваше завдання як студента першого курсу в академії — точно і швидко обчислити, скільки тріблів буде для заданого числа 'Тріббоначчі'. Факт у тому, що обчислення вищезгаданої рекурентної формули рекурсивно повільніше, ніж хімічна тяга для міжзоряних подорожей! Робити це для більш ніж кількох поколінь було б явно нелогічно.
Вхідні дані
Перша строка вхідних даних буде містити ціле число t (0 < t < 69), що представляє кількість тестових випадків. Після цього буде t цілих чисел, по одному на рядок. Кожне з них буде представляти номер покоління g (0 ≤ g ≤ 67), яке потрібно обчислити.
Вихідні дані
Для кожного зчитаного номера покоління виведіть відповідне значення 'Тріббоначчі'.