Поколения трибблов
Трибблы — это милые, пушистые существа с ненасытным аппетитом и невероятной скоростью размножения, которая может соперничать с любым сложным организмом в галактике (трибблы рождаются уже беременными!). После того как их завезли на Энтерпрайз, экипаж быстро понял, какой проблемой могут стать трибблы. Вскоре они заполонили весь корабль.
К счастью для Энтерпрайза, инженер Скотт смог транспортировать их на ближайший клингонский корабль. Клингоны не знали о проблемах, которые могут вызвать трибблы, и привезли их в клингонское пространство, где трибблы распространились как саранча, разрушая экосистемы планет по всей Клингонской Империи.
Члены Объединенной Федерации Планет (Федерация) нашли это чрезвычайно забавным и использовали вычисление размножения трибблов как академическое упражнение для студентов первого курса в своей академии.
Следующая последовательность чисел показывает, как размножаются трибблы. Первое число соответствует поколению 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), для которого нужно произвести вычисление.
Выходные данные
Для каждого введенного номера поколения выведите соответствующее значение 'Триббоначчи'.