T = int(raw_input())
MOD = 1000000009
MX = 100000
dp = [1] * MX

for i in xrange(0, 9):
    for coin in xrange(i + 1, MX):
        dp[coin] = (dp[coin] + dp[coin - (1 + i)]) % MOD

for i in xrange(T):
    k = int(raw_input())
    k //= 111111

    print dp[k]