#include <iostream>

using namespace std;

const long long MOD = 1000000009LL;
const int COIN_TYPES = 10;
const long long COINS[1 + COIN_TYPES] = { 
	0, 
	1, 
	111111 / 111111, 
	222222 / 111111, 
	333333 / 111111, 
	444444 / 111111,
	555555 / 111111, 
	666666 / 111111, 
	777777 / 111111, 
	888888 / 111111, 
	999999 / 111111
};
const long long MAX_NUMBER = 10000000000LL / 111111L;
long long patterns[1 + COIN_TYPES][1 + MAX_NUMBER];

int main() {
	patterns[0][0] = 1;
	for (int k = 1; k <= MAX_NUMBER; ++k) {
		patterns[0][k] = 0;
	}
	for (int i = 1; i <= COIN_TYPES; ++i) {
		patterns[i][0] = 1;
		for (int k = 1; k <= MAX_NUMBER; ++k) {
			patterns[i][k] = patterns[i - 1][k];
			if (k - COINS[i] >= 0) {
				patterns[i][k] += patterns[i][k - COINS[i]];
				patterns[i][k] %= MOD;
			}
		}
	}
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		long long m;
		cin >> m;
		m = m - m % 111111;
		m /= 111111;
		cout << patterns[COIN_TYPES][m] << endl;
	}
	return 0;
}