n = int(input())
c = [1,2,4] # 1,2,3을 가지고 1,2,3을 만들 수 있는 경우의 수 ex) (1), ((1,1),(2)),((1,1,1,1)(1,2)(2,1)(3)) 

for j in range(3,11): # ex)4 번째 숫자 = 1의 개수 + 2의 개수 + 3의 개수
    c.append(c[j-3] + c[j-2] + c[j-1]) 
for i in range(n):
    k = int(input())
    print(c[k-1])        

# 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는 3에서 더해진 숫자들에서 1을 더한것 + 2에서 더해진 숫자에서 2를 더한것 1에서 더해진 숫자에서 3을 더한 것

