#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define pcnt __builtin_popcount
#define show(x) cout<<#x<<" = "<<x<<endl;
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define fi first
#define se second
#define rng(a) a.begin(),a.end()
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define sz(x) (int)(x).size()

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
template<typename T>string join(vector<T>&v)
{stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
ll gcd(ll a,ll b){if(a>b)swap(a,b);for(;a>0;b%=a,swap(a,b));return b;}
int modpow(ll a,ll n,int m){if(a==0)return a;ll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(int)p;}
void dout(double d){printf("%.12f\n",d);}

const int iinf = 1e9;
const ll linf = 1e18;
const int mod = 1e9+9;
const double eps = 1e-10;
const ll V[21] = {
  1, 99, 2450, 7350, 8600, 0,
  1, 49, 225, 350, 0,
  1, 9, 20, 0,
  1, 4, 0,
  1, 0,
  1
};
const ll G[100][5] = {
  1,0,0,0,0,
  1,1,0,0,0,
  1,2,1,0,0,
  1,3,2,0,0,
  1,4,4,0,0,
  1,5,6,0,0,
  1,6,9,0,0,
  1,7,12,0,0,
  1,8,16,0,0,
  1,9,20,0,0,
  1,10,25,1,0,
  1,11,30,2,0,
  1,12,36,4,0,
  1,13,42,6,0,
  1,14,49,9,0,
  1,15,56,12,0,
  1,16,64,16,0,
  1,17,72,20,0,
  1,18,81,25,0,
  1,19,90,30,0,
  1,20,100,37,1,
  1,21,110,44,2,
  1,22,121,53,4,
  1,23,132,62,6,
  1,24,144,73,9,
  1,25,156,84,12,
  1,26,169,97,16,
  1,27,182,110,20,
  1,28,196,125,25,
  1,29,210,140,30,
  1,30,225,158,37,
  1,31,240,176,44,
  1,32,256,197,53,
  1,33,272,218,62,
  1,34,289,242,73,
  1,35,306,266,84,
  1,36,324,293,97,
  1,37,342,320,110,
  1,38,361,350,125,
  1,39,380,380,140,
  1,40,400,414,159,
  1,41,420,448,178,
  1,42,441,486,201,
  1,43,462,524,224,
  1,44,484,566,251,
  1,45,506,608,278,
  1,46,529,654,309,
  1,47,552,700,340,
  1,48,576,750,375,
  1,49,600,800,410,
  1,50,625,855,451,
  1,51,650,910,492,
  1,52,676,970,539,
  1,53,702,1030,586,
  1,54,729,1095,639,
  1,55,756,1160,692,
  1,56,784,1230,751,
  1,57,812,1300,810,
  1,58,841,1375,875,
  1,59,870,1450,940,
  1,60,900,1531,1014,
  1,61,930,1612,1088,
  1,62,961,1699,1171,
  1,63,992,1786,1254,
  1,64,1024,1879,1346,
  1,65,1056,1972,1438,
  1,66,1089,2071,1539,
  1,67,1122,2170,1640,
  1,68,1156,2275,1750,
  1,69,1190,2380,1860,
  1,70,1225,2492,1982,
  1,71,1260,2604,2104,
  1,72,1296,2723,2238,
  1,73,1332,2842,2372,
  1,74,1369,2968,2518,
  1,75,1406,3094,2664,
  1,76,1444,3227,2822,
  1,77,1482,3360,2980,
  1,78,1521,3500,3150,
  1,79,1560,3640,3320,
  1,80,1600,3788,3506,
  1,81,1640,3936,3692,
  1,82,1681,4092,3894,
  1,83,1722,4248,4096,
  1,84,1764,4412,4314,
  1,85,1806,4576,4532,
  1,86,1849,4748,4766,
  1,87,1892,4920,5000,
  1,88,1936,5100,5250,
  1,89,1980,5280,5500,
  1,90,2025,5469,5770,
  1,91,2070,5658,6040,
  1,92,2116,5856,6330,
  1,93,2162,6054,6620,
  1,94,2209,6261,6930,
  1,95,2256,6468,7240,
  1,96,2304,6684,7570,
  1,97,2352,6900,7900,
  1,98,2401,7125,8250,
  1,99,2450,7350,8600
};

vvl matl;
vpii idxl;
map<pii, int> idxh;
void merge(vl&a, vl&b, vl&c){
  vl tmp;
  tmp.resize(21);
  FOR(s, 0, 21){
    ll t = 0;
    int i = idxl[s].fi, j = idxl[s].se;
    FOR(k, i, j+1){
      FOR(l, k, j+1){
        t += a[idxh[pii(i, k)]] * b[idxh[pii(l, j)]];
        t %= mod;
      }
    }
    tmp[s] = t;
  }
  FOR(i, 0, 21)c[i] = tmp[i];
}
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  FOR(i, 0, 6)FOR(j, i, 6){
    idxh[pii(i, j)] = sz(idxl);
    idxl.pb(pii(i, j));
  }
  matl.resize(63);
  matl[0].resize(21);
  FOR(i, 0, 21)matl[0][i] = V[i];
  FOR(i, 1, 63){
    matl[i].resize(21);
    merge(matl[i-1], matl[i-1], matl[i]);
  }
  int t;
  cin >> t;
  FOR(i, 0, t){
    ll m, n;
    cin >> m;
    n = m % 500;
    n /= 5;
    m /= 500;
    if(m==0){
      ll ans = 0;
      FOR(j, 0, 5)ans += G[n][j];
      cout << ans%mod << endl;
      continue;
    }
    int c = 0;
    while(!(m&1)){
      c++;
      m /= 2;
    }
    vl h = matl[c];
    c++;
    m /= 2;
    while(m > 0){
      if(m&1)merge(matl[c], h, h);
      c++;
      m /= 2;
    }
    ll ans = 0;
    FOR(j, 0, 5){
      FOR(k, j, 6){
        FOR(l, k, 6){
          ans += G[n][j] * h[idxh[pii(k, l)]];
          ans %= mod;
        }
      }
    }
    cout << ans << endl;
  }
}