#yuki_41

z=111111
mod=1000000009
mx=100000
dp=[[1 for i in xrange(mx)] for j in xrange(11)]
for i in xrange(1,10):
 for j in xrange(mx):
  dp[i][j]=dp[i-1][j]
  if j-i>=0:
   dp[i][j]+=dp[i][j-i]
   dp[i][j]%=mod
   
t=int(raw_input())
print
while t>0:
 m=int(raw_input())
 ta=m/z
 
 res=dp[9][ta]
 t-=1
 print res