mod = 10**9+9
M = 10**5
dp = [0]*M
dp[0] = 1
lis = [i for i in range(1,10)]+[1]
for l in lis:
    for i in range(M):
        if i + l < M:
            dp[i+l] += dp[i]
            dp[i+l] %= mod

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