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

using ll = long long;
constexpr int mod = 1e9 + 9;

int main(void) {
	const int N = 100000;
	vector<ll> dp(N, 0);
	for(int i = 0; i < N; ++i) dp[i] = i + 1;
	
	for(int c = 2; c <= 9; ++c) for(int i = 0; i + c < N; ++i) dp[i + c] = (dp[i + c] + dp[i]) % mod;
	
	int T;
	cin >> T;
	while(T--) {
		ll M;
		cin >> M;
		
		M /= 111111;
		cout << dp[M] << "\n";
	}
	
	return 0;
}