#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#define LL long long


using namespace std;


const LL MOD = (LL)1e9 + 9;
struct V{
	LL num[12];
	LL *f = num;
	LL *sub = num + 6;
	LL& operator[](int i){
		return num[i];
	}
	void operator=(V another){
		for (int i = 0; i < 12; i++){
			num[i] = another[i];
		}
	}
	V operator+(V &another){
		V res;
		for (int i = 0; i < 12; i++){
			res[i] = (num[i] + another[i])%MOD;
		}
		return res;
	}
	LL operator*(V &another){
		LL res=0;
		for (int i = 0; i < 12; i++){
			res += num[i] * another[i];
			res %= MOD;
		}
		return res;
	}
};

struct M{
	V row[15];
	V& operator[](int i){
		return row[i];
	}
	void operator=(M another){
		for (int i = 0; i < 12; i++)
			for (int j = 0; j < 12; j++){
				row[i][j] = another[i][j];
			}
	}
	M operator+(M &another){
		M res;
		for (int i = 0; i < 12; i++){
			res[i] = (row[i] + another[i]);
		}
		return res;
	}
	M operator*(M &another){
		M res;
		for (int i = 0; i < 12; i++){
			for (int j = 0; j < 12; j++){
				res[i][j] = 0;
				for (int k = 0; k < 12; k++){
					res[i][j] += row[i][k] * another[k][j];
				}
				res[i][j] %= MOD;
			}
		}
		return res;
	}
	V operator*(V &another){
		V res;

		for (int i = 0; i < 12; i++){
			res[i] = 0;
			for (int j = 0; j < 12; j++)	
				res[i] += row[i][j] * another[j];
			res[i] %= MOD;
		}
		return res;
	}
};


const LL YEN[] = { 1, 5, 10, 50, 100, 500 };


V dpf[6][501];
V dpsub[6][501];
LL ALL[6][501];
LL SUB[6][501];
#define LOGN 61
M m[LOGN];
void init(){
	for (int i = 0; i < 6; i++){
		dpf[i][0].f[i] = 1;
		dpsub[i][0].sub[i] = 1;
	}
	for (int i = 1; i <= 500; i++){
		dpf[0][i].f[0] = dpsub[0][i].sub[0] = 1;
	}
	for (int i = 1; i < 6; i++){
		for (LL j = YEN[i]; j <= 500; j+=YEN[i]){
			for (int k = 0; k < 6; k++){
				dpsub[i][j] = dpsub[i][j - YEN[i]] + dpf[i - 1][j - YEN[i]];
				dpf[i][j] = dpsub[i][j] + dpf[i-1][j];
			}
		}
	}

	for (int i = 0; i < 6; i++){
		m[0].row[i] = dpf[i][500];
		m[0].row[i + 6] = dpsub[i][500];
	}
	for (int i = 1; i < LOGN; i++){
		m[i] = m[i - 1] * m[i - 1];
	}

	for (int i = 0; i < 501; i++){
		SUB[0][i] = ALL[0][i] = 1;
	}
	for (int i = 1; i < 6; i++){
		for (LL j = YEN[i]; j <=500; j++){
			SUB[i][j] = (SUB[i][j - YEN[i]] + ALL[i - 1][j - YEN[i]]) % MOD;
		}
		for (LL j = 0; j <= 500; j++){
			ALL[i][j] = (SUB[i][j] + ALL[i - 1][j]) % MOD;
		}
	}

}
int main(){
	int T;
	LL n;
	cin >> T;

	init();
	while (T--){
		cin >> n;
		M matrix;
		
		for (int i = 0; i < 12; i++){
			for (int j = 0; j < 12; j++){
				matrix[i][j] = 0;
			}
			matrix[i][i] = 1;
		}
		
		V res;
		for (int i = 0; i < 6; i++){
			res[i] = ALL[i][n%500];
			res[i + 6] = SUB[i][n%500];
		}
		/*
		for (int i = 0; i < 6; i++){
			matrix.row[i] = dpf[i][n%500];
			matrix.row[i + 6] = dpsub[i][n%500];
		}
		*/
		n /= 500;
		for (int i = 0; i < LOGN; i++){
			if (n & 1)matrix = m[i]*matrix;
			n >>= 1;
		}
		res = matrix*res;
		cout << res[5] << endl;
	}



}