Generations of Tribbles

Koong has nothing to do in the army. So he wants to build a Fibonacci sequence of his own. The usual Fibonacci is too simple for him, so he wanted something heavier, and he came up with the sequence below. Writing his own Fibonacci function as $koong(n)$,

n < 2 :                         1
n = 2 :                         2
n = 3 :                         4
n > 3 : koong(n - 1) + koong(n - 2) + koong(n - 3) + koong(n - 4)

Compute Koong's Fibonacci yourself.

The first line contains the number of test cases $t$ ($0 < t < 69$). Each of the next $t$ lines contains one integer $n$ ($0 \le n \le 67$), the index of the Fibonacci value to compute.

For each test case, print Koong's Fibonacci value on its own line.