import sys

def prob22():
  def binomial(n, m):
    if m < 0 or m > n:
      return 0

    v = 1
    if m > n // 2:
      m = n - m
    for i in range(1, m + 1):
      v = v * (n + 1 - i) // i
    return v
  
  coefs = [1, 2, 4, 6, 9, 12, 16, 20, 25, 30, 37, 44, 53, 62, 73, 84, 97, 110, 125, 140, 159, 178, 201, 224, 251, 278, 309, 340, 375, 410, 451, 492, 539, 586, 639, 692, 751, 810, 875, 940, 1014, 1088, 1171, 1254, 1346, 1438, 1539, 1640, 1750, 1860, 1982, 2104, 2238, 2372, 2518, 2664, 2822, 2980, 3150, 3320, 3506, 3692, 3894, 4096, 4314, 4532, 4766, 5000, 5250, 5500, 5770, 6040, 6330, 6620, 6930, 7240, 7570, 7900, 8250, 8600, 8975, 9350, 9750, 10150, 10575, 11000, 11450, 11900, 12375, 12850, 13355, 13860, 14395, 14930, 15495, 16060, 16655, 17250, 17875, 18500, 19156, 19812, 20499, 21186, 21904, 22622, 23371, 24120, 24900, 25680, 26492, 27304, 28148, 28992, 29868, 30744, 31652, 32560, 33500, 34440, 35409, 36378, 37376, 38374, 39401, 40428, 41484, 42540, 43625, 44710, 45821, 46932, 48069, 49206, 50369, 51532, 52721, 53910, 55125, 56340, 57574, 58808, 60061, 61314, 62586, 63858, 65149, 66440, 67750, 69060, 70382, 71704, 73038, 74372, 75718, 77064, 78422, 79780, 81150, 82520, 83891, 85262, 86634, 88006, 89379, 90752, 92126, 93500, 94875, 96250, 97615, 98980, 100335, 101690, 103035, 104380, 105715, 107050, 108375, 109700, 111000, 112300, 113575, 114850, 116100, 117350, 118575, 119800, 121000, 122200, 123360, 124520, 125640, 126760, 127840, 128920, 129960, 131000, 132000, 133000, 133951, 134902, 135804, 136706, 137559, 138412, 139216, 140020, 140775, 141530, 142227, 142924, 143563, 144202, 144783, 145364, 145887, 146410, 146875, 147340, 147744, 148148, 148491, 148834, 149116, 149398, 149619, 149840, 150000, 150160, 150256, 150352, 150384, 150416, 150384, 150352, 150256, 150160, 150000, 149840, 149619, 149398, 149116, 148834, 148491, 148148, 147744, 147340, 146875, 146410, 145887, 145364, 144783, 144202, 143563, 142924, 142227, 141530, 140775, 140020, 139216, 138412, 137559, 136706, 135804, 134902, 133951, 133000, 132000, 131000, 129960, 128920, 127840, 126760, 125640, 124520, 123360, 122200, 121000, 119800, 118575, 117350, 116100, 114850, 113575, 112300, 111000, 109700, 108375, 107050, 105715, 104380, 103035, 101690, 100335, 98980, 97615, 96250, 94875, 93500, 92126, 90752, 89379, 88006, 86634, 85262, 83891, 82520, 81150, 79780, 78422, 77064, 75718, 74372, 73038, 71704, 70382, 69060, 67750, 66440, 65149, 63858, 62586, 61314, 60061, 58808, 57574, 56340, 55125, 53910, 52721, 51532, 50369, 49206, 48069, 46932, 45821, 44710, 43625, 42540, 41484, 40428, 39401, 38374, 37376, 36378, 35409, 34440, 33500, 32560, 31652, 30744, 29868, 28992, 28148, 27304, 26492, 25680, 24900, 24120, 23371, 22622, 21904, 21186, 20499, 19812, 19156, 18500, 17875, 17250, 16655, 16060, 15495, 14930, 14395, 13860, 13355, 12850, 12375, 11900, 11450, 11000, 10575, 10150, 9750, 9350, 8975, 8600, 8250, 7900, 7570, 7240, 6930, 6620, 6330, 6040, 5770, 5500, 5250, 5000, 4766, 4532, 4314, 4096, 3894, 3692, 3506, 3320, 3150, 2980, 2822, 2664, 2518, 2372, 2238, 2104, 1982, 1860, 1750, 1640, 1539, 1438, 1346, 1254, 1171, 1088, 1014, 940, 875, 810, 751, 692, 639, 586, 539, 492, 451, 410, 375, 340, 309, 278, 251, 224, 201, 178, 159, 140, 125, 110, 97, 84, 73, 62, 53, 44, 37, 30, 25, 20, 16, 12, 9, 6, 4, 2, 1]

  stdin = sys.stdin
  T = int(stdin.readline())
  K = 6
  MOD = 10 ** 9 + 9
  l = 100
  for _ in range(T):
    N = int(stdin.readline())
    N //= 5
    k, m = divmod(N, l)
    ans = 0
    b = binomial(k + K - 1, K - 1)
    while m < len(coefs) and m <= N:
      ans += coefs[m] * b
      m += l
      k -= 1
      b = b * (k + 1) // (k + K)
    print(ans % MOD)

prob22()