#include <bits/stdc++.h>
using namespace std;

#define REP(i, n) for(ll i = 0; i < (ll)(n); i++)
#define FOR(i,n,m) for (ll i=n; i < (ll)(m); i++)
#define INF 1000000009
#define pb push_back
#define MAX_Md 100000

typedef long long ll;

int T;
ll just_dp[MAX_Md]; //丁度n枚を表す
ll dp[MAX_Md+1]={0};

int main(){
    just_dp[0]=1;
    FOR(i,1,10){
        REP(j,MAX_Md){
            just_dp[i + j]+=just_dp[j];
            just_dp[i + j]%=INF;
        }
    }
    
    dp[0]=0;
    REP(i,MAX_Md){
        dp[i+1]=dp[i]+just_dp[i];
        dp[i+1]%=INF;
    }
    
    cin >> T;
    REP(i,T){
        ll M;
        cin >> M;
        cout << dp[M/111111+1] << endl;
    }
    
    return 0;
}