import sys


def input(): return sys.stdin.readline().rstrip()


class Poly:
    """
    Class Denoting Polynomial
    """
    MOD = 10**9+9

    def __init__(self, poly):
        self.poly = poly

    def __mul__(self, other):
        ret = [0]*(len(self.poly)+len(other.poly)-1)
        for i in range(len(self.poly)):
            for j in range(len(other.poly)):
                ret[i+j] = (ret[i+j]+self.poly[i]*other.poly[j]) % Poly.MOD
        return Poly(ret)

    def __add__(self, other):
        ret = self.poly[:] + [0]*max(0, len(other.poly)-len(self.poly))
        for i in range(len(other.poly)):
            ret[i] = (ret[i] + other.poly[i]) % Poly.MOD

        while len(ret) > 1 and ret[-1] == 0:
            ret.pop()
        return Poly(ret)

    def __sub__(self, other):
        ret = self.poly[:] + [0]*max(0, len(other.poly)-len(self.poly))
        for i in range(len(other.poly)):
            ret[i] = (ret[i] - other.poly[i]) % Poly.MOD

        while len(ret) > 1 and ret[-1] == 0:
            ret.pop()
        return Poly(ret)

    def substitute(self, other):
        x = Poly([self.poly[-1]])
        for i in self.poly[-2::-1]:
            x = x * other + Poly([i])

        return x

    def accumulated(self):
        degree = len(self.poly)-1

        P = [Poly([1])]
        Q = [Poly([1])]
        for i in range(degree+1):
            P.append(P[-1]*Poly([0, 1]))
            Q.append(Q[-1]*Poly([-1, 1]))

        ret = [0]*(degree+2)
        remaining = Poly(self.poly[:])
        for i in range(degree+1, 0, -1):
            delta = P[i] - Q[i]
            c = remaining.poly[i-1] * \
                pow(delta.poly[i-1], -1, Poly.MOD) % Poly.MOD
            remaining -= delta * Poly([c])
            ret[i] = c

        ret[0] = self.poly[0]
        return Poly(ret)


def main():
    D = [Poly([1])]
    for i in [5, 10, 50, 100, 500]:
        D = [D[j % len(D)].substitute(
            Poly([j // len(D), i // len(D)])).accumulated() for j in range(i)]

    T = int(input())
    for i in range(T):
        M = int(input())
        print(D[M % 500].substitute(Poly([M // 500])).poly[0])


if __name__ == '__main__':
    main()