#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
const ll MOD = 1000000009;

template <typename T>
struct matrix{
    int n, m;
    vector<vector<T>> dat;
    matrix(int n_, int m_){
        n = n_; m = m_;
        for(int i = 0; i < n; i++){
            dat.push_back(vector<T>(m));
        }
    }
};

template <typename T>
bool prod(matrix<T> a, matrix<T> b, matrix<T> &ans){
    if(a.m != b.n) return false;
    for(int i = 0; i < a.n; i++){
        for(int j = 0; j < b.m; j++){
            ans.dat[i][j] = 0;
            for(int k = 0; k < b.n; k++){
                ans.dat[i][j] += (a.dat[i][k]*b.dat[k][j])%MOD;
                ans.dat[i][j] %= MOD;
            }
        }
    }
    return true;
}

template <typename T>
void copy_mat(matrix<T> a, matrix<T> &b){
    for(int i = 0; i < a.n; i++){
        for(int j = 0; j < a.m; j++){
            b.dat[i][j] = a.dat[i][j];
        }
    }
}

template <typename T>
void pow(matrix<T> a, ll n, matrix<T> &ans){
    matrix<T> buf(a.n, a.n);
    matrix<T> tmp(a.n, a.n);
    copy_mat(a, tmp);

    for(int i = 0; i < a.n; i++) {
        for(int j = 0; j < a.n; j++){
            ans.dat[i][j] = 0;
        }
        ans.dat[i][i] = 1;
    }
    
    for(int i = 0; i <= 60; i++){
        ll m = (ll)1 << i;
        if(m&n){
            prod(tmp, ans, buf);
            copy_mat(buf, ans);
        }
        prod(tmp, tmp, buf);
        copy_mat(buf, tmp);
    }
}


template <typename T>
void print_mat(matrix<T> a){
    for(int i = 0; i < a.n; i++){
        for(int j = 0; j < a.m; j++){
            cout << a.dat[i][j] << ' ';
        }
        cout << endl;
    }
}

ll dp[6][505];
int coin[6] = {1, 5, 10, 50, 100, 500};
matrix<ll> mat(6, 6);

ll calc(int l, int r){
    for(int i = 0; i <= 500; i++){
        for(int j = 0; j < 6; j++){
            dp[j][i] = 0;
        }
    }
    dp[l][0] = 1;
    for(int i = 0; i < 500; i++){
        for(int j = l; j <= r; j++){
            for(int k = j; k <= r; k++){
                if(i+coin[k] <= 500){
                    dp[k][i+coin[k]] += dp[j][i];
                    dp[k][i+coin[k]] %= MOD;
                }
            }
        }
    }
    return dp[r][500];
}

void init(){
    for(int i = 0; i < 6; i++){
        for(int j = 0; j < 6; j++){
            mat.dat[i][j] = calc(i, j);
        }
    }
    for(int i = 0; i <= 500; i++){
        for(int j = 0; j < 6; j++){
            dp[j][i] = 0;
        }
    }
    dp[0][0] = 1;
    for(int i = 0; i < 500; i++){
        for(int j = 0; j < 6; j++){
            for(int k = j; k < 6; k++){
                if(i+coin[k] <= 500){
                    dp[k][i+coin[k]] += dp[j][i];
                    dp[k][i+coin[k]] %= MOD;
                }
            }
        }
    }
}

void solve(){
    ll m;
    cin >> m;
    int rem = m%500;
    ll n = m/500;
    matrix<ll> vec(1, 6), ans(1, 6);
    for(int i = 0; i < 6; i++) vec.dat[0][i] = dp[i][rem];
    matrix<ll> buf(6, 6);
    pow<ll>(mat, n, buf);
    // print_mat(buf);
    // print_mat(vec);
    prod(vec, buf, ans);
    ll ret = 0;
    for(int i = 0; i < 6; i++){
        ret += ans.dat[0][i];
        ret %= MOD;
    }
    cout << ret << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    init();
    // print_mat(mat);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++){
        solve();
    }
}