MOD = 10 ** 9 + 9
n = int(input())
dp = [1] * 100100
for i in range(1, 10):
    for j in range(100000):
        dp[j + i] = (dp[j + i] + dp[j]) % MOD
for _ in range(n):
    m = int(input())
    print(dp[m // 111111])