9095

import sys
input = sys.stdin.readline

n = int(input())
test = [0]*n
for i in range(n):
    test[i] = int(input())

def dpsum(t):
    if t == 1:
        return 1
    elif t == 2:
        return 2
    elif t == 3:
        return 4
    else:
        return dpsum(t-1)+dpsum(t-2)+dpsum(t-3)

result = [0]*n
for i in range(n):
    result[i] = dpsum(test[i])

print(*result, sep='\n')

 

#동적계획법