MOD = 10 ** 9 + 9 dp = [1] * 10 ** 5 for k in range(1, 10): for i in range(k, 10 ** 5): dp[i] += dp[i - k] dp[i] %= MOD for _ in range(int(input())): print(dp[int(input()) // 111111])