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

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

Технические условия

Вход:В первой сроке задано число T - количество тестовых случаев в тесту. Во последующих строках задано T чисел - индексы искомых членов новой последовательности.
1 <= T <= 1000
Выход: T строк с найденными членами новой последовательности.
Количество цифр в каждом искомом числе не превышает 2005.

Информация о задаче

Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 1
Сложность: 59% 41/100

Пример

Пример входных данных

3
3 6 9

Пример выходных данных

1
7
49

← Зоопарк

Список задач