import sys
input = sys.stdin.readline

N = 2 * 10 ** 5
mod = 10 ** 9 + 9
dp = [0] * N
dp[0] = 1
for j in range(1, 10):
    for i in range(1, N):
        if i - j >= 0:
            dp[i] += dp[i - j]
            dp[i] %= mod

Ac = [0] * (N + 1)
for i in range(N):
    Ac[i + 1] = Ac[i] + dp[i]
    Ac[i + 1] %= mod

T = int(input())
for _ in range(T):
    print(Ac[int(input())//111111 + 1])