i,s[99999];
long m=1e9+9;
main(j){
for(i=0;i<91e3;i++)s[i]=1;
for(i=1;i<=9;i++)for(j=0;j<9e4;s[i+j++]%=m)s[j+i]+=s[j];
for(gets(&i);~scanf("%ld",&m);)printf("%d\n",s[m/111111]);
return 0;
}