$dp = Hash.new 1
def f(n)
  (0...9).each{|i|
    (i+1...n).each{|j|
      $dp[j] += $dp[j-i-1]
      $dp[j] %= 10**9+9
    }
  }
end

T = gets.to_i
M = T.times.map{ gets.to_i }
f(1+10**10/111111)
M.each{|m|
  p $dp[m/111111]
}