MOD = 10 ** 9 + 9
for _ in range(int(input())):
    m = int(input())
    x = m // 111111
    dp = [0] * (x + 1)
    dp[0] = 1
    for i in range(1,10):
        for j in range(x):
            if i + j <= x:
                dp[i+j] += dp[j]
                dp[i+j] %= MOD
    print(sum(dp)%MOD)