[백준][동적 계획법 1] No.9461_파도반 수열 完

# ---------- Function ----------
def padovan(N):
    # padovan_list[1], padovan_list[2], padovan_list[3] = 1, 1, 1
    if N == 1 or N == 2 or N == 3:
        return 1
    
    if padovan_list[N] != 0:
        return padovan_list[N]
    
    padovan_list[N] = padovan(N-2) + padovan(N-3)
    
    return padovan_list[N]

# ---------- Main ----------
caseT = int(input())

for _ in range(caseT):
    N = int(input())
    padovan_list = [0] * (N+1)
    print(padovan(N))