#include using namespace std; namespace { typedef long long ll; ll T; ll M; void solve(); void doit() { cin >> T; for (auto i = 0; i < T; i++) { cin >> M; solve(); } } /** output whole vector. ex) vector{1, 2, 3} -> '1 2 3'. */ template ostream& operator<<(ostream& os, const vector& xs) { if (xs.empty()) return os; os << xs[0]; for (auto i = 1; i < xs.size(); i++) os << ' ' << xs[i]; return os; } void solve() { const ll unit = 111*1000 + 111; const ll MOD = ll(1e9 + 9); auto m = M / unit; vector> g(m + 1, vector(10, 0)); for (auto x = 0; x <= m; x++) { g[x][0] = 1; for (auto k = 1; k <= 9; k++) { g[x][k] = g[x][k - 1]; if (x - k >= 0) { g[x][k] = (g[x][k] + g[x - k][k]) % MOD; } //g[x][k] = 0; //for (auto t = 0; t * k <= x; t++) { // g[x][k] = (g[x][k] + g[x - t * k][k - 1]) % MOD; //} } } //cout << "==g==" << endl; //for (auto i = 0; i <= m; i++) cout << g[i][9] << " "; //cout << endl; ll ans = g[m][9]; cout << ans << endl; } } int main() { doit(); return 0; }