#include <iostream>
#include <algorithm>
using namespace std;
using i64 = long long;

class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;
public:range(int n):i({0}),n({n}){}range(int i,int n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};

template <int mod>
struct Modint {
  long long x;
  Modint(void) : Modint(0) {};
  Modint(long long x) : x((x%mod+mod)%mod) {};
  Modint operator + (const Modint a)    { return Modint(*this) += a; }
  Modint operator - (const Modint a)    { return Modint(*this) -= a; }
  Modint operator * (const Modint a)    { return Modint(*this) *= a; }
  Modint operator * (const long long a) { return Modint(*this) *= Modint(a); }
  Modint operator +=(const Modint& a)   { if((x+=a.x)>=mod) { x-=mod; } return *this; }
  Modint operator -=(const Modint& a)   { if((x-=a.x)<0) { x+=mod; } return *this; }
  Modint operator *=(const Modint& a)   { (x*=a.x)%=mod; return *this; }
  Modint operator *=(const long long a) { (x*=a)%=mod; return *this; }
  /* a++ */ Modint operator ++(int)     { Modint old; old.x = x; if((x+=1)>=mod) { x-=mod; }; return old; }
  /* ++a */ Modint operator ++(void)    { *this += 1; return *this; }
  /* a-- */ Modint operator --(int)     { Modint old; old.x = x; if((x-=1)<0) { x+=mod; }; return old; }
  /* --a */ Modint operator --(void)    { *this -= 1; return *this; }
  bool operator ==(const Modint& a) const   { return x == a.x; }
  bool operator ==(const long long a) const { return x == Modint(a); }
  bool operator !=(const Modint& a) const   { return !(x == a.x); }
  bool operator !=(const long long a) const { return !(x == Modint(a)); }
  int intvalue(void) const { return (int)x; }
};
const int mod = 1000000009;
using modint = Modint<mod>;

const int MAX = pow(10, 10) / 111111;
vector<modint> dp;

int main(void) {
  dp.assign(MAX, 1);
  for(int v : range(1, 10)) {
    for(int cost : range(v, MAX)) {
      dp[cost] += dp[cost-v];
    }
  }
  int t; scanf("%d", &t);
  for(int cases : range(t)) {
    i64 m; scanf("%lld", &m);
    m /= 111111;
    modint res = dp[m];
    printf("%d\n", res.intvalue());
  }
  return 0;
}