T=int(raw_input())
dp=[1 for j in range(100001)]
mod=1000000009
for j in range(1,10):
    for i in range(100001):
        if i-j < 0:
            continue
        dp[i] += dp[i-j]
        dp[i]%=mod


for i in range(T):
    M= int(raw_input())
    t=M/111111
    print dp[t]