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

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

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

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

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

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

Вхідні дані

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

Вихідні дані

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

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

Приклад

Вхідні дані #1
3
3
6
9
Вихідні дані #1
1
7
49