Задачі
Нова послідовність Фібоначчі
Нова послідовність Фібоначчі
Нова послідовність Фібоначчі утворюється наступним чином: перші чотири члени послідовності рівні одиниці, а кожен наступний член послідовності дорівнює сумі чотирьох попередніх.
Знайти N
-й член нової послідовності Фібоначчі.
Вхідні дані
У першому рядку задано число T
- кількість тестових випадків у тесті. У наступних рядках задано T
чисел - номери шуканих членів нової послідовності. 1 ≤ T ≤ 1000
Вихідні дані
T
рядків зі знайденими членами нової послідовності.
Кількість цифр у кожному шуканому числі не перевищує 2008.
Приклад
Вхідні дані #1
3 3 6 9
Вихідні дані #1
1 7 49