DFS - 백준 9095. 1,2,3의 합으로 n을 만드는 방법 수

t = int(input())

def DFS(sum):
    global count
    global n
    if sum == n:
        count += 1
    elif sum > n:  # 단순하지만 이것도 백트래킹이라고 할 수 있겠지..?
        return
    else:
        for i in range(1, 4):
            DFS(sum + i)

for j in range(t):
    n = int(input())
    count = 0
    DFS(0)
    print(count)