15988

def plus(count):
    dp = [0 for i in range(1000001)]
    dp[0]=0
    dp[1]=1
    dp[2]=2
    dp[3]=4
        
    

    for x in range(4,1000001):
        dp[x]=(dp[x-3]+dp[x-2]+dp[x-1])%1000000009

    for i in range(0, count):
        print(dp[int(input())])

plus(int(input()))