[백준][동적 계획법/DP] 9095. 1, 2, 3 더하기

import sys
input = sys.stdin.readline

def solution(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    else:
        return solution(n-1)+solution(n-2)+solution(n-3)

t = int(input())

for _ in range(t):
    print(solution(int(input())))