#include "bits/stdc++.h"
using namespace std;

long long mod = (long long)1e9 + 9;


vector<vector<long long>> fmatrix(int N){
	vector<vector<long long>> ret(N, vector<long long>(N));
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (i == j) ret[i][j] = 1;
			else ret[i][j] = 0;
		}
	}
	return ret;
}

vector<vector<vector<long long>>> mulboard;

vector<vector<long long>> matrixmul(vector<vector<long long>> v1){
	int N = v1.size();
	vector<vector<long long>> ret(N, vector<long long>(N));
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			for (int k = 0; k < N; k++)
			{
				ret[i][j] += v1[i][k] * v1[k][j];
				if (k != 0) ret[i][j] -= v1[i][k - 1] * v1[k][j];
				ret[i][j] %= mod;
				ret[i][j] += mod;
				ret[i][j] %= mod;
			}
		}
	}
	return ret;
}

vector<int> cost;

#define MAX 500
long long dp[6][6][MAX + 1];

long long nowdp[6];
long long nextdp[6];

int main() {
	cost.push_back(1);
	cost.push_back(5);
	cost.push_back(10);
	cost.push_back(50);
	cost.push_back(100);
	cost.push_back(500);
	
	vector<vector<long long>> firstboard(6, vector<long long>(6));
	for (int t = cost.size() - 1; t >= 0; t--)
	{
		for (int i = 0; i < cost.size(); i++)
		{
			for (int j = 0; j <= MAX; j++)
			{
				dp[t][i][j] = 0;
			}
		}
		dp[t][t][0] = 1;

		for (int i = 0; i < cost.size(); i++)
		{
			for (int j = 0; j <= MAX; j++)
			{
				if (i > 0) dp[t][i][j] += dp[t][i - 1][j];
				if (j >= cost[i]) dp[t][i][j] += dp[t][i][j - cost[i]];
				dp[t][i][j] %= mod;
			}
		}

		for (int i = 0; i < cost.size(); i++)
		{
			firstboard[t][i] = dp[t][i][MAX];
		}
	}

	auto nowboard = firstboard;
	mulboard.push_back(nowboard);
	for (int i = 0; i < 62; i++)
	{
		nowboard = matrixmul(nowboard);
		mulboard.push_back(nowboard);
	}

	int T;
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		long long M;
		cin >> M;
		long long p = M / MAX;
		for (int j = 0; j < 6; j++)
		{
			nowdp[j] = 0;
			nextdp[j] = 0;
		}
		for (int j = 0; j < 6; j++)
		{
			nowdp[j] = dp[0][j][M%MAX];
		}

		int count = 0;
		while (p > 0){
			if (p % 2 == 1){
				for (int i = 0; i < 6; i++)
				{
					for (int j = 0; j < 6; j++)
					{
						nextdp[j] += nowdp[i] * mulboard[count][i][j];
						if (i != 0)
							nextdp[j] -= nowdp[i - 1] * mulboard[count][i][j];
					}
				}

				for (int j = 0; j < 6; j++)
				{
					nowdp[j] = nextdp[j] % mod;
					if (nowdp[j] < 0) nowdp[j] += mod;
					nextdp[j] = 0;
				}
			}
			count++;
			p /= 2;
		}

		long ans = nowdp[5] % mod;
		cout << ans << endl;
	}
}