e-olymp
Задачі

Нова послідовність Фібоначчі

Нова послідовність Фібоначчі

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

Знайти N-й член нової послідовності Фібоначчі.

Вхідні дані

У першому рядку задано число T - кількість тестових випадків у тесті. У наступних рядках задано T чисел - номери шуканих членів нової послідовності. 1 ≤ T ≤ 1000

Вихідні дані

T рядків зі знайденими членами нової послідовності.

Кількість цифр у кожному шуканому числі не перевищує 2008.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані
3
3 6 9


Вихідні дані
1
7
49