/* -*- coding: utf-8 -*- * * 41.cc: No.41 貯金箱の溜息(EASY) - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ typedef long long ll; const ll MAX_M = 10000000000LL; const int MAX_X = (int)(MAX_M / 111111); const ll MOD = 1000000009; /* typedef */ /* global variables */ ll dp[MAX_X + 1], dsum[MAX_X + 1]; /* subroutines */ /* main */ int main() { dp[0] = 1; for (int i = 1; i <= 9; i++) for (int x = 0; x <= MAX_X - i; x++) dp[x + i] = (dp[x] + dp[x + i]) % MOD; dsum[0] = dp[0]; for (int x = 1; x <= MAX_X; x++) dsum[x] = (dsum[x - 1] + dp[x]) % MOD; int tn; cin >> tn; while (tn--) { ll mi; cin >> mi; printf("%lld\n", dsum[(int)(mi / 111111)]); } return 0; }