#yuki638

t=int(raw_input())
dp=[1]*100000

for i in xrange(0,9):
 for j in xrange(i+1,100000):
  dp[j]=(dp[j]+dp[j-(i+1)])%(10**9+9)

for i in xrange(t):
 m=int(raw_input())
 m/=111111
 print dp[m]