MOD = 10 ** 9 + 9
m = 10 ** 10
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

for i in range(x):
    dp[i + 1] += dp[i]
    dp[i + 1] %= MOD
for _ in range(int(input())):
    print(dp[int(input()) // 111111])