import std.algorithm;
import std.array;
import std.ascii;
import std.container;
import std.conv;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void log(A...)(A arg) {
    stdout.writeln(arg);
}
int size(T)(in T s) {
    return cast(int)s.length;
}

void main() {
    const long mod = cast(long)(1e9 + 9);
    long[] C = [1, 5, 10, 50, 100, 500];
    int T = readln.chomp.to!int;
    foreach (_; 0 .. T) {
        long M = readln.chomp.to!long;
        long[] W;
        long[] sum;
        void init() {
            long m = 1;
            for (; m <= M; m <<= 1) {
                foreach (c; C) {
                    if (0 < m * c && m * c <= M) {
                        W ~= m * c;
                    }
                }
            }
            W.sort!"a > b";
            sum = new long[W.size + 1];
            for (int i = W.size - 1; i >= 0; i--) {
                auto w = W[i];
                sum[i] = sum[i + 1] + w;
                if (sum[i] < 0) sum[i] = long.max;
            }
        }
        init();

        long[Tuple!(int, long)] cache;
        long dfs(int n, long x) {
            if (x == 0) return 1;
            if (n == W.size || x < 0) return 0;
            if (sum[n] < x) return 0;
            auto key = tuple(n, x);
            if (key in cache) return cache[key];
            //log([n], [x], (dfs(n + 1, x) + dfs(n + 1, x - W[n])) % mod);
            return cache[key] = (dfs(n + 1, x) + dfs(n + 1, x - W[n])) % mod;
        }
        
        writeln(dfs(0, M));
    }
}