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