T=int(input())
mod=10**9+9
N=10**6
dp=[0]*N
dp[0]=1
for c in range(1,10):
    for i in range(c,N):
        dp[i]+=dp[i-c]
        dp[i]%=mod
for t in range(T):
    M=int(input())
    ans=0
    for x in range(M//111111+1):
        ans+=dp[x]
        ans%=mod
    print(ans)