mod = 10**9+9
N = 10**5
DP = [0] * (N+10)
DP[0] = 1
for j in range(1,10):
    for i in range(N):
        DP[i+j] += DP[i]
        DP[i+j] %= mod
S = [0] * (N+10)
for i in range(N):
    S[i] = S[i-1] + DP[i]
    S[i] %= mod
T = int(input())
for _ in range(T):
    M = int(input())
    print(S[M//111111])