[백준, 9095번] 1, 2, 3 더하기

# 재귀를 활용해 푼 풀이
def cycle(n):
    global cnt
    if n == 0: 
        cnt += 1
        return 
    for i in range(1,4): # 1~3까지의 수만으로 입력하기에
        if n-i >= 0: cycle(n-i)

for i in range(int(input())):
    n = int(input())
    cnt = 0
    cycle(n)
    print(cnt)

 

# 규칙을 활용한 DP 풀이법
# n번째의 수는 n-1 + n-2 + n-3 의 값이 된다는 것을 활용
for _ in range(int(input())):
    n = int(input())
    dp = [0]*11
    dp[1], dp[2], dp[3] = 1, 2, 4
    for i in range(4, n+1):
        dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
    print(dp[n])