import sys
input = sys.stdin.readline

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