T = gets.to_i
MOD = 10 ** 9 + 9
dp = Array.new(101000, 0)
dp[0] = 1

1.upto(9) do |d|
  100000.times do |i|
    dp[d + i] += dp[i]
    dp[d + i] %= MOD
  end
end

ans = Array.new(101000, 0)
ans[0] = 1

1.upto(100000) do |i|
  ans[i] = ans[i - 1] + dp[i]
  ans[i] %= MOD
end

T.times do
  m = gets.to_i

  puts ans[m / 111_111]
end