eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

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

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

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

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

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

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

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

Пример

Входные данные #1
3
3
6
9
Выходные данные #1
1
7
49