e-olymp
Problems

New number Fibonacci (RU)

New number Fibonacci (RU)

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

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

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

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

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

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

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

Time limit 1 second
Memory limit 64 MiB
Input example
3
3 6 9


Output example
1
7
49