Yeni Fibonaççi ardıcıllığı belə yaradılmışdır: ardıcıllığın ilk dörd həddi vahidə bərabərdir, sonra gələn hər bir hədd özündən əvvəlki dörd həddin cəminə bərabərdir. Yeni Fibonaççi ardıcıllığının N-ci həddini tapın.

Giriş verilənləri

Birinci sətirdə testlərin T sayı verilir. Sonrakı sətirdə T sayda ədəd - yeni ardıcıllığın axtarılan hədlərinin indeksləri verilir. 1 ≤ T ≤ 1000.

Çıxış verilənləri

T sayda sətirdə yeni ardıcıllığın tapılmış olan hədləri. Hər tapılan ədəddə rəqəmlərin sayı 2008-i aşmır.