/* -*- coding: utf-8 -*- * * 3277.cc: No.3277 Forever Monotonic Number - yukicoder */ #include #include #include using namespace std; /* constant */ const int MAX_L = 15; const int MOD = 998244353; /* typedef */ using ll = long long; using vl = vector; template struct MI { int v; MI(): v() {} MI(int _v): v(_v % MOD) { if (v < 0) v += MOD; } MI(long long _v): v(_v % MOD) { if (v < 0) v += MOD; } explicit operator int() const { return v; } MI operator+(const MI m) const { return MI(v + m.v); } MI operator-(const MI m) const { return MI(v + MOD - m.v); } MI operator-() const { return MI(MOD - v); } MI operator*(const MI m) const { return MI((long long)v * m.v); } MI &operator+=(const MI m) { return (*this = *this + m); } MI &operator-=(const MI m) { return (*this = *this - m); } MI &operator*=(const MI m) { return (*this = *this * m); } bool operator==(const MI m) const { return v == m.v; } bool operator!=(const MI m) const { return v != m.v; } MI pow(long long n) const { // a^n % MOD MI pm = 1, a = *this; while (n > 0) { if (n & 1) pm *= a; a *= a; n >>= 1; } return pm; } MI inv() const { return pow(MOD - 2); } MI operator/(const MI m) const { return *this * m.inv(); } MI &operator/=(const MI m) { return (*this = *this / m); } }; using mi = MI; /* global variables */ ll ts[MAX_L + 1]; vl fms; mi inv9 = mi(9).inv(); /* subroutines */ void rec(int l, int d, ll s) { if (l <= 0) { int dsum = 0; for (ll m = s; m > 0; m /= 10) dsum += m % 10; auto vit = lower_bound(fms.begin(), fms.end(), (ll)dsum); if (vit != fms.end() && *vit == dsum) fms.push_back(s); return; } if (d >= 10) return; for (int i = l; i >= 0; i--) rec(l - i, d + 1, s * ts[i] + (ts[i] - 1) / 9 * d); } /* main */ int main() { ts[0] = 1; for (int i = 0; i < MAX_L; i++) ts[i + 1] = ts[i] * 10; for (int i = 1; i <= 9; i++) fms.push_back(i); for (int l = 2; l <= MAX_L; l++) rec(l, 1, 0); //printf(" fms=%d\n", (int)fms.size()); //for (auto f: fms) printf(" %lld", f); putchar('\n'); int tn; scanf("%d", &tn); while (tn--) { ll n; scanf("%lld", &n); if (n == 0) { puts("1"); continue; } n++; //printf("n=%lld\n", n); auto vit = lower_bound(fms.begin(), fms.end(), n); //printf(" f=%lld\n", *vit); ll s0 = *vit - n; ll c9 = s0 / 8; int r = s0 % 8; ll c1 = n - (c9 + 1); //printf(" c1=%lld,r=%d,c9=%lld\n", c1, r, c9); mi tc9 = mi(10).pow(c9), tc1 = mi(10).pow(c1), tn = mi(10).pow(n); //mi sum = (tc1 - 1) * inv9; //sum = sum * 10 + (r + 1); //sum = sum * tc9 + (tc9 - 1) * inv9 * 9; mi sum = (tn - 1) * inv9 + tc9 * r + (tc9 - 1) * inv9 * 8; printf("%d\n", (int)sum); } return 0; }