#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 9;

template <class T>
struct Matrix {
    vector<vector<T>> A;

    Matrix() {}

    Matrix(size_t n, size_t m) : A(n, vector<T>(m, 0)) {}

    Matrix(size_t n) : A(n, vector<T>(n, 0)){};

    size_t height() const {
        return (A.size());
    }

    size_t width() const {
        return (A[0].size());
    }

    inline const vector<T>& operator[](int k) const {
        return (A.at(k));
    }

    inline vector<T>& operator[](int k) {
        return (A.at(k));
    }

    static Matrix I(size_t n) {
        Matrix mat(n);
        for (int i = 0; i < n; i++)
            mat[i][i] = 1;
        return (mat);
    }

    Matrix& operator+=(const Matrix& B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                (*this)[i][j] += B[i][j];
        return (*this);
    }

    Matrix& operator-=(const Matrix& B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                (*this)[i][j] -= B[i][j];
        return (*this);
    }

    Matrix& operator*=(const Matrix& B) {
        size_t n = height(), m = B.width(), p = width();
        assert(p == B.height());
        vector<vector<T>> C(n, vector<T>(m, 0));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                for (int k = 0; k < p; k++)
                    C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]);
        A.swap(C);
        return (*this);
    }

    Matrix& operator^=(long long k) {
        Matrix B = Matrix::I(height());
        while (k > 0) {
            if (k & 1)
                B *= *this;
            *this *= *this;
            k >>= 1LL;
        }
        A.swap(B.A);
        return (*this);
    }

    Matrix operator+(const Matrix& B) const {
        return (Matrix(*this) += B);
    }

    Matrix operator-(const Matrix& B) const {
        return (Matrix(*this) -= B);
    }

    Matrix operator*(const Matrix& B) const {
        return (Matrix(*this) *= B);
    }

    Matrix operator^(const long long k) const {
        return (Matrix(*this) ^= k);
    }

    friend ostream& operator<<(ostream& os, Matrix& p) {
        size_t n = p.height(), m = p.width();
        for (int i = 0; i < n; i++) {
            os << "[";
            for (int j = 0; j < m; j++) {
                os << p[i][j] << (j + 1 == m ? "]\n" : ",");
            }
        }
        return (os);
    }


    T determinant() {
        Matrix B(*this);
        assert(width() == height());
        T ret = 1;
        for (int i = 0; i < width(); i++) {
            int idx = -1;
            for (int j = i; j < width(); j++) {
                if (B[j][i] != 0)
                    idx = j;
            }
            if (idx == -1)
                return (0);
            if (i != idx) {
                ret *= -1;
                swap(B[i], B[idx]);
            }
            ret *= B[i][i];
            T vv = B[i][i];
            for (int j = 0; j < width(); j++) {
                B[i][j] /= vv;
            }
            for (int j = i + 1; j < width(); j++) {
                T a = B[j][i];
                for (int k = 0; k < width(); k++) {
                    B[j][k] -= B[i][k] * a;
                }
            }
        }
        return (ret);
    }
};
template <uint Mod>
struct ModInt {
    using M = ModInt;
    const static M G;
    uint v;
    ModInt(long long _v = 0) { set_v(uint(_v % Mod + Mod)); }
    M& set_v(uint _v) {
        v = (_v < Mod) ? _v : _v - Mod;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + Mod - r.v); }
    M operator*(const M& r) const { return M().set_v((unsigned long long)v * r.v % Mod); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(long long n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1)
                r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(Mod - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
    friend istream& operator>>(istream& is, M& r) { return is >> r.v; }
};

int main() {
    const int C[] = {1, 5, 10, 50, 100, 500};

    ModInt<MOD> dp[510][10] = {};
    dp[0][0] = 1;
    for (int i = 0; i < 6; i++) {
        for (int c = 0; c <= 500; c++) {
            if (c + C[i] <= 500)
                dp[c + C[i]][i] += dp[c][i];
            dp[c][i + 1] += dp[c][i];
        }
    }

    Matrix<ModInt<MOD>> Mat(6);
    for (int t = 0; t < 6; t++) {
        ModInt<MOD> dp[510][10] = {};
        dp[0][t] = 1;
        for (int i = 0; i < 6; i++) {
            for (int c = 0; c <= 500; c++) {
                if (c + C[i] <= 500)
                    dp[c + C[i]][i] += dp[c][i];
                if (c > 0)
                    dp[c][i + 1] += dp[c][i];
            }
        }
        for (int i = 0; i < 6; i++) {
            Mat[i][t] = dp[500][i];
        }
    }


    int T;
    cin >> T;
    while (T--) {
        long long M;
        cin >> M;
        Matrix<ModInt<MOD>> Vec(6, 1);
        for (int i = 0; i < 6; i++) {
            Vec[i][0] = dp[M % 500][i];
        }
        Matrix<ModInt<MOD>> Mat_M = (Mat ^ (M / 500));
        Vec = Mat_M * Vec;
        cout << Vec[5][0] << endl;
    }
}