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

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

#ifdef LOCAL
auto operator<<(auto& o, auto x) -> decltype(x.first, o);
auto operator<<(auto& o, auto x) -> decltype(x.end(), o) {
  o << "{";
  for (int i = 0; auto y : x) o << ", " + !i++ * 2 << y;
  return o << "}"; }
auto operator<<(auto& o, auto x) -> decltype(x.first, o) {
  return o << "(" << x.first << ", " << x.second << ")"; }
void __print(auto... x) { ((cerr << x << " "), ...) << endl; }
#define debug(x...) __print("[" #x "]:", x)
#else
#define debug(...) 2137
#endif

using I = __int128;
const I INF = 1e35;
int n;
string s;

I wart(string x) {
  I ans = 0;
  rep(i, 0, sz(x)) ans = ans * 10 + x[i] - '0';
  return ans;
}
string str(int d, I x) {
  string ans;
  rep(i, 0, d) {
    ans += '0' + x % 10;
    x /= 10;
  }
  reverse(all(ans));
  return ans;
}

I licz(vector<string> w, vi nzer) {
  //debug(w, nzer);
  int r = sz(w), c = sz(w[0]);
  I ans = INF;
  auto spr = [&](int poz, I v) {
    bool ok = 1;
    rep(i, 0, r) {
      I x = v - (poz - i);
      if (x <= 0) {
        ok = 0;
        break;
      }
      string xs = str(c, x);
      rep(j, 0, c) if (w[i][j] != '?' && xs[j] != w[i][j]) {
        ok = 0;
        break;
      }
      if (xs[nzer[i]] == '0') {
        ok = 0;
        break;
      }
    }
    if (ok) ans = min(ans, v - poz);
    //if (ans == 0) debug(poz, (int)v, ok);
  };
  rep(zm, 0, c) {
    rep(d, '0', '9' + 1) rep(poz, 1, r) {
      // liczymy
      string x = w[poz];
      x[zm] = d;
      rep(i, zm + 1, c) x[i] = '0';
      I v = wart(x);
      //if (zm == 0) debug(d, poz, x, w[poz]);
      spr(poz, v);
    }
    // wypelniamy kolumne w lcp
    bool nie0 = 0;
    char czyx = 0;
    rep(i, 0, r) {
      if (w[i][zm] != '?') {
        if (czyx && czyx != w[i][zm]) return ans;
        czyx = w[i][zm];
      }
      if (zm == nzer[i]) nie0 = 1;
    }
    //debug(zm, nie0, czyx);
    char x;
    if (czyx) {
      if (czyx == '0' && nie0 == 1) return ans;
      x = czyx;
    } else {
      x = nie0 ? '1' : '0';
    }
    rep(i, 0, r) w[i][zm] = x;
  }
  if (r == 1) ans = min(ans, wart(w[0]));
  return ans;
}

I rozw(vector<pii> pr) {
  int m = sz(pr);
  vector<string> w(m);
  rep(i, 0, m) {
    auto [l, r] = pr[i];
    rep(j, l, r) {
      if (j < 0 || j >= n) w[i] += '?';
      else w[i] += s[j];
    }
  }
  vi nzer(m);
  bool czy = 0;
  rep(i, 0, m) {
    if (sz(w[i]) < sz(w.back())) {
      czy = 1;
      nzer[i] = 1;
      w[i] = '0' + w[i];
    } else if (czy) {
      if (w[i][0] != '?' && w[i][0] != '1') return INF;
      w[i][0] = '1';
    }
  }
  return licz(w, nzer);
}

I suma(I x) { // pozycja 1szej
  I odp = 1;
  I y = 1;
  while (y <= x) {
    odp += x - y;
    y *= 10;
  }
  return odp;
}

void solve() {
  cin >> s;
  n = sz(s);
  I ans = INF;
  rep(d, 1, n + 2) rep(wys, 0, d) {
    int mxi = (n - (d - wys) + (d - 1)) / d + 1;
    rep(male, 0, mxi + 1) {
      vector<pii> pr;
      int l = -wys;
      rep(i, 0, male) {
        if (l >= n) break;
        pr.push_back({l, l + d});
        l += d;
      }
      while (l < n) {
        pr.push_back({l, l + d + 1});
        l += d + 1;
      }
      I x = rozw(pr);
      //if (x != INF) debug((int)x);
      if (x != INF) ans = min(ans, suma(x) + wys);
    }
  }
  cout << int(ans % 998244353) << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) solve();
}