T = int(input()) MAX = 1000000 dp = [0] * MAX dp2 = [0] * MAX mod = 10 ** 9 + 9 dp[0] = 1 for i in range(1, 10): for j in range(MAX - i): dp[i + j] += dp[j] if dp[i + j] >= mod: dp[i + j] -= mod dp2[0] = 1 for i in range(1, MAX): dp2[i] = dp2[i - 1] + dp[i] if dp2[i] >= mod: dp2[i] -= mod for i in range(T): M = int(input()) M /= 111111 print(dp2[int(M)])