# 1, 2, 3 더하기 문제
# 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지이다. 합을 나타낼 때는 수를 1개이상 사용해야 한다.
# 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 프로그램을 작성하시오
# 예시는 n은 양수이며, 11보다 작다.
# https://www.acmicpc.net/problem/9095

# 접근방법: 숫자 '1'을 만드는 방법은 1개 / 숫자 '2'를 만드는 방법은 2개 - 1+1, 2 / 숫자 '3'은 4개 - 1+1+1, 2+1, 1+2, 3
# 숫자 '4'는 7개 - 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 1+3
# 숫자 '5'는 13개 - 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+1+3, 1+3+1, 3+1+1, 1+2+2, 2+1+2, 2+2+1, 2+3, 3+2
# 이처럼 다시 보면 규칙이 있다 / 숫자 4를 만드는 가지를 잘 보면 1+3, 2+2, 3+1 이렇게 보면 뒷숫자 3, 2, 1를 만드는 경우 수를 구할 수 있다.
# 이거를 수식으로 나타내어 정리하면 숫자 4를 만드는 경우는 3을 만드는 경우, 2를 만드는 경우, 1를 만드는 경우를 더하면 7로 나온다.
# 수식을 대문자 I로 하고, I(n) = I(n-1) + I(n-2) + I(n-3) 단, n>3
'''
I = [1, 2, 4]
for n in range(4, 11):
    I.append(I[n-1]+I[n-2]+I[n-3])
for _ in range(int(input())):
    print(d[int(input())])
'''

# 동적계획법이라는 방법
# 사실은 나도 이런 방법의 의미를 모르겠음
# 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효울적으로 값을 구하는 알고리즘 설계 기법
t_count = int(input())
ins_list = []

int_list = [1, 2, 4]
for i in range(4, 11):
    int_list.append(sum(int_list[-3:]))

for i in range(t_count):
    ins_list.append(int(input()))

for i in range(t_count):
    print(int_list[ins_list[i] - 1])
