'''
규칙을 살펴보자.
1 = (1)
2 = (1 + 1), (2)
3 = (1 + 1 + 1), (1 + 2), (2 + 1), (3)
4 = (1 + 1 + 1 + 1), (1 + 1 + 2), (1 + 2 + 1), (1 + 3), (2 + 1 + 1), (2 + 2), (3 + 1)
4에서 맨처음 더해지는 숫자들 4개를 보자.
1에 위의 3에서 더해졌던 숫자들이 더해지는것을 볼 수 있다.
그 다음 2에 2에서 더해졌던 숫자들이 더해진다.
3은 1에서 더해졌던 숫자들이 더해진다.
4는
1 + 3
2 + 2
3 + 1로 나타낼 수 있는데, 3의 개수, 2의 개수, 1의 개수를 다 더해주면 4의 개수가 된다.
'''
import sys
sys.stdin = open('input.txt','r')

#N이 1일때 1가지, 2일때 2가지 3일때 4가지, 점화식은 N >3일떄부터!
dp = [1,2,4]
for n in range(3,12):
    dp.append(dp[n-1] + dp[n-2] + dp[n-3])
T = int(input())
for tc in range(1,T+1):
    N = int(input())
    print(dp[N-1])
