e-olymp
Задачи

Новый ряд Фибоначчи

Новый ряд Фибоначчи

Новая последовательность Фибоначчи образована таким образом: первые четыре члены последовательности равны единице, а каждый последующий член последовательности равен сумме четырех предыдущих.

Найти N-й член новой последовательности Фибоначчи.

Входные данные

В первой сроке задано число T - количество тестовых случаев в тесту. Во последующих строках задано T чисел - индексы искомых членов новой последовательности. 1 ≤ T ≤ 1000

Выходные данные

T строк с найденными членами новой последовательности.

Количество цифр в каждом искомом числе не превышает 2008.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
3
3 6 9


Выходные данные
1
7
49