#include <cstdio>

typedef long long ll;

const ll MOD = 1e9 + 9;

int T;
ll M;

ll perm_inv[7];

ll expt(ll a, ll n){
    ll res = 1ll;
    while(n > 0){
        if(n & 1){res = res * a % MOD;}
        n >>= 1;
        a = a * a % MOD;
    }
    return res;
}

ll nCk(ll n, ll k){
    if(n < 0 || k < 0 || n < k){return 0ll;}

    ll res = 1ll;
    for(ll i=n;i>n-k;i--){
        res = i % MOD * res % MOD;
    }

    return res * perm_inv[k] % MOD;
}

ll nHk(ll n, ll k){
    if(n == 0 && k == 0){return 1ll;}
    return nCk(n+k-1, k);
}

ll solve(){
    ll res = 0ll;

    for(int i1=M%5;i1<500;i1+=5){
        for(int i5=(M-i1)%10/5;i5<100;i5+=2){ // 5 (2)
            if(i5 < 0){continue;}
            for(int i10=(M-i1-i5*5)%50/10;i10<50;i10+=5){ // 10 (5)
                if(i10 < 0){continue;}
                for(int i50=(M-i1-i5*5-i10*10)%100/50;i50<10;i50+=2){ // 50 (2)
                    if(i50 < 0){continue;}
                    int i100 = (M-i1-i5*5-i10*10-i50*50)%500/100;
                    ll diff = M - (1ll * i1 + i5 * 5 + i10 * 10 + i50 * 50 + i100 * 100);
                    if(i100 < 0 || diff < 0){continue;}
                    // printf("%d, %d, %d, %d, %d: %lld\n", i1, i5, i10, i50, i100, nHk(diff/500+1, 5));
                    res = (res + nHk(diff/500+1, 5)) % MOD;               
                }
            }
        }
    }

    return res;
}

int main(){
    perm_inv[0] = 1;
    for(int i=1;i<=6;i++){
        perm_inv[i] = perm_inv[i-1] * expt(i, MOD-2) % MOD;
    }
    
    scanf("%d", &T);

    for(int i=0;i<T;i++){
        scanf("%lld", &M);

        printf("%lld\n", solve());
    }
}