#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD = 1000000009;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    int dp[100000] = {};
    dp[0] = 1;
    for (int i = 1; i <= 9; i++) {
        for (int j = 0; j < 100000; j++) {
            if (i + j >= 100000) continue;
            (dp[i + j] += dp[j]) %= MOD;
        }
    }
    for (int i = 1; i < 100000; i++) (dp[i] += dp[i - 1]) %= MOD;
    for (int testcase = 0; testcase < t; testcase++) {
        ll m;
        cin >> m;
        cout << dp[m / 111111] << endl;
    }
    return 0;
}