#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int MOD = (int)1e9 + 9;

int main() {
    const int ZORO = 111111;
    const int MAX = 1e10 / ZORO;
    vector<int> dp(MAX + 1, 1);
    for (int i = 1; i <= 9; i++) {
        for (int j = i; j <= MAX; j++) (dp[j] += dp[j - i]) %= MOD;
    }
    int T; cin >> T;
    while (T--) {
        long long M; cin >> M;
        cout << dp[M / ZORO] << endl;
    }
    return 0;
}