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

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

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

Вхідні дані

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

Вихідні дані

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

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

Приклади