#include <bits/stdc++.h> using namespace std; typedef long long ll; #define REP(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) REP(i,0,n) int const MOD = 1e9 + 9; int const BASE = 111111; int dp[BASE+1]; int main() { rep(i, BASE) dp[i] = 1; REP(i, 1, 10) REP(j, i, BASE) (dp[j] += dp[j-i]) %= MOD; int Tc; cin >> Tc; rep(_, Tc) { ll M; cin >> M; cout << dp[M/BASE] << endl; } return 0; }