mo = int(1e9) + 9
MAX = 1000000
dp = [0] * MAX
sum = [0] * MAX

T = int(input())
dp[0] = 1
for i in range(1, 10):
    for j in range(MAX - i):
        dp[i + j] += dp[j]
        if dp[i + j] >= mo:
            dp[i + j] -= mo

sum[0] = 1
for i in range(1, MAX):
    sum[i] = sum[i - 1] + dp[i]
    if sum[i] >= mo:
        sum[i] -= mo

for i in range(T):
    M = int(input())
    M //= 111111
    print(sum[M])