#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(int)(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;

class ModInt {
    long long value_;

public:
    static long long Mod;
    static void set_mod(long long mod) { Mod= mod; }
    static long long  get_mod(void) { return Mod; }

    ModInt() : value_(0) {}
    ModInt(long long val) {
            if (val >= Mod)
                value_ = val % Mod;
            else if (val >= 0)
                value_ = val;
            else // val < 0
                value_ = (((-val)/Mod+1)*Mod+val) % Mod;
            assert(value_ < Mod);
    }
    ModInt(const ModInt &other) { value_ = other.value_; }
    ~ModInt() {}

#define OPT(OP)                                                         \
    ModInt operator OP (const ModInt &other) const {                    \
        return ModInt(value_ OP other.value_);                          \
    }                                                                   \
    template<class T>                                                   \
    ModInt &operator OP##=(const T &other) {                            \
        return (*this = (*this OP ModInt(other)));                      \
    }
    OPT(+) OPT(-) OPT(*)
#undef OPT

    bool operator==(const ModInt &other) const {
        return (value_ == other.value_);
    }
    bool operator!=(const ModInt &other) const {
        return !(*this == other);
    }
    ModInt &operator=(const ModInt &other) {
        value_ = other.value_;
        return *this;
    }
    // cast overload
    operator int() const { return value_; }
    operator long long() const { return value_; }
    long long value() const { return value_; }
    friend std::ostream& operator<<(std::ostream& os, const ModInt& m) {
        os<<m.value_;
        return os;
    }
};
#define OPT(OP,T)                                                        \
    ModInt operator OP (const ModInt &a, T b) { return a OP ModInt(b); } \
    ModInt operator OP (T a, const ModInt &b) { return ModInt(a) OP b; }
    OPT(*,int) OPT(+,int) OPT(-,int) OPT(*,long long) OPT(+,long long) OPT(-,long long)
#undef  OPT
long long ModInt::Mod = (long long)(1E+9)+9;

template<typename T>
T extgcd(T a, T b, T &x, T &y) {
    T d = a;
    if (b != 0)
    {
        d = extgcd(b, a%b, y, x);
        y -= (a/b)*x;
    }
    else
    {
        x=1; y=0;
    }
    return d;
}

ModInt inverse(const ModInt &a) {
        ll x,y;
        auto gcd = extgcd((ll)a, ModInt::Mod, x, y);
        if (gcd != 1)
            return 0;
        return x;
}
class SighOfSavingsBox {
public:
    void solve(void) {
            // M <= 10^18 なので M に対する DP ではダメ。どう高速化するか？
            //
            // f(x,m) := C[x] 以下の coin を使って m 円をちょうど払う方法の数
            //
            // とすると,
            //
            // f(x,m) = f(x-1,m) + f(x-1,m-C[x]) + f(x-1,m-2*C[x]) + ... + f(x-1,m-k*C[x]) (k*C[x] <= m) ...(*)
            // であり
            //
            // f(x,m-C[x]) = f(x-1,m-C[x]) + ... + f(x-1,m-k*C[x]) より
            // f(x,m) = f(x-1,m) + f(x,m-C[x]) と書ける
            //
            // このままだと m が大きすぎて計算できない。
            //
            // f(0,m) = 1 (0 次の多項式)であり p を未満の任意の整数とすると
            //
            // f(x,m*C[x]+p)     - f(x,(m-1)*C[x]+p) = f(x-1,m*C[x]+p)
            // f(x,(m-1)*C[x]+p) - f(x,(m-2)*C[x]+p) = f(x-1,(m-1)*C[x]+p)
            //    :
            // f(x,C[x]+p)       - f(x,p)          = f(x-1,C[x]+p)
            //
            // なので
            //
            // f(x,m*C[x]+p) = f(x,p) + f(x-1,m*C[x]+p) + ... + f(x-1,C[x]+p)
            //                          <---------------- m ---------------->
            //
            // g(x) を d 次多項式とすると
            // g(x-k) = x^d + G(x-k) と書けるので
            //
            // x                 x
            // ∑ g(y)  = x*x^d + ∑ G(x-k)  となり d+1 次式となる。
            // y=1               k=1
            //
            // よって f(x,m*C[x]+p) は再帰的に m についての x 次式となる
            //
            // ( f(x,m) が x 次式になるわけではないことに注意!!!
            //   なぜなら (*) における k は k=m/C[x] であってこの値はかなり大きい )
            //
            // この x 次多項式の係数ををラグランジェ補完によって決定してやればよい。
            //
            // この多項式 f(x,m*C[x]+p) は p に依存する。
            //
            const vector<int> C = {1,5,10,50,100,500};

            // 多項式を補完するためにサンプル点を準備
            // 多項式は p に依存するためサンプルは多めにとっておく
            int K = C.size();
            int x = K-1;
            int nSamples = C[x]*(K+1) + 1;
            vector<vector<ModInt>> dp(K+1, vector<ModInt>(nSamples));

            // 初期化
            // C[0]=1 で表現できるのは 1 通り
            fill(RANGE(dp[0]), 1);

            // O(nSamples*K)
            FOR(x,1,K)
            REP(m,nSamples)
            {
                dp[x][m] = dp[x-1][m];
                if (m >= C[x])
                    dp[x][m] += dp[x][m-C[x]];
            }


            int T;
            cin>>T;
            REP(_,T)
            {
                ll M;
                cin>>M;

                //
                // sample を使って f(x,m*C[x]+p) をラグランジェ補完して
                //  m = M/C[x]
                //  p = M%C[x]
                // を代入する
                ModInt res = 0;
                ll m = M/C[x];
                ll p = M%C[x];
                // O(K^2*log(K))
                REP(i, K)
                {
                    ModInt c = 1;
                    REP(j, K)
                    {
                        if (i == j)
                            continue;
                        c *= (m-j);
                        c *= inverse(i-j);
                    }
                    res += dp[x][i*C[x]+p]*c;
                }
                cout<<res<<endl;
            }
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new SighOfSavingsBox();
        obj->solve();
        delete obj;
        return 0;
}
#endif