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

Найти N-й член новой последовательности Фибоначчи.

Входные данные

В первой сроке задано число T - количество тестовых случаев в тесту. Во последующих строках задано T чисел - индексы искомых членов новой последовательности. 1 ≤ T ≤ 1000

Выходные данные

T строк с найденными членами новой последовательности.

Количество цифр в каждом искомом числе не превышает 2008.