#include <array>
#include <cassert>
#include <iostream>
#include <set>
#include <utility>
#include <vector>

using namespace std;

const int MOD = 998244353;

bool smaller(const vector<int>& a, const vector<int>& b) {
  if(a.size() != b.size()) return a.size() < b.size();
  for(int i = 0; i < a.size(); i++) {
    if(a[i] != b[i]) return a[i] < b[i];
  }
  return false;
}

void addone(vector<int>& val) {
  for(int i = val.size()-1; i >= 0; i--) {
    if(++val[i] == 10) {
      val[i] = 0;
      if(i == 0) val.insert(val.begin(), 1);
    }
    else break;
  }
}
void subtractone(vector<int>& val) {
  for(int i = val.size()-1; i >= 0; i--) {
    if(--val[i] == -1) {
      val[i] = 9;
      assert(i > 0);
    }
    else break;
  }
}

bool checkconsistency(const string& s, const vector<array<int, 2>>& curr) {
  for(int i = 0; i < s.size(); i++) {
    if(s[i] == '?') continue;
    int want = s[i] - '0';
    if(want == curr[i][0]) continue;
    return false;
  }
  return true;
}

void genvals(vector<array<int, 2>>& curr, vector<int>& val, int desiredlength) {
  while(curr.size() < desiredlength) {
    for(int i = 0; i < val.size(); i++) {
      curr.push_back({val[i], i});
    }
    if(curr.size() < desiredlength) addone(val);
  }
}

bool match(const vector<int>& have, const vector<int>& want) {
  for(int i = 0; i < want.size(); i++) {
    if(want[i] == -1) continue;
    if(have[i] != want[i]) return false;
  }
  return true;
}

bool validstart(vector<int> cand, const vector<int>& before, const vector<int>& after) {
  if(cand[0] == 0) return false;
  if(!match(cand, before)) return false;
  addone(cand);
  if(!match(cand, after)) return false;
  return true;
}

bool checknocarry(const int len, const int offset, const int unitdigit, const string& s, vector<int>& ret) {
  string padded = "";
  for(int i = 0; i < offset; i++) padded += "?";
  padded += s;
  while(padded.size() % len) padded += "?";
  vector<vector<pair<string, int>>> constraintsv(2);
  int seenzero = 0;
  for(int start = 0; start < padded.size(); start += len) {
    if(start && (unitdigit + start/len)%100 == 0) seenzero = 1;
    constraintsv[seenzero].emplace_back(padded.substr(start, len), (unitdigit + start/len)%100);
  }
  assert(len >= 3);
  vector<vector<int>> base(2, vector<int>(len-2, -1));
  int idx = 0;
  for(const auto& constraints: constraintsv) {
    for(auto constraint: constraints) {
      string want = constraint.first;
      assert(want.size() == len);
      int lasttwo = constraint.second;
      if(want[len-1] != '?' && want[len-1]-'0' != lasttwo%10) return false;
      if(want[len-2] != '?' && want[len-2]-'0' != lasttwo/10) return false;
      for(int i = 0; i < len-2; i++) {
        if(want[i] != '?') {
          int use = want[i] - '0';
          if(base[idx][i] != -1 && base[idx][i] != use) return false;
          base[idx][i] = use;
        }
      }  
    }
    idx++;
  }
  vector<int> bestcand;
  for(int nines = 0; nines < len-2; nines++) {
    vector<int> cand(len-2, -1);
    // set the nines
    for(int a = 0; a < nines; a++) cand[len-3-a] = 9;
    // set the changing digit
    int idx = len-3-nines;
    bool invalid = false;
    if(base[0][idx] == -1 && base[1][idx] == -1) {
      // both unconstrained, go for zero
      cand[idx] = 0;
    }
    else if(base[0][idx] == -1) {
      // top is constrained
      cand[idx] = (base[1][idx] + 9) % 10;
    }
    else if(base[1][idx] == -1) {
      // bottom is constrained
      cand[idx] = (base[0][idx]);
    }
    else {
      if((base[0][idx]+1)%10 != base[1][idx]) {
        invalid = true;
      }
      else cand[idx] = base[0][idx];
    }
    // all other digits must be immutable
    idx--;
    while(!invalid && idx >= 0) {
      if(base[0][idx] == -1 && base[1][idx] == -1) {
        // both unconstrained, go for zero
        cand[idx] = 0;
      }
      else if(base[0][idx] == -1) {
        cand[idx] = (base[1][idx]);
      }
      else if(base[1][idx] == -1) {
        // bottom is constrained
        cand[idx] = (base[0][idx]);
      }
      else {
        if(base[0][idx] != base[1][idx]) {
          invalid = true;
        }
        else cand[idx] = base[0][idx];
      }
      idx--;
    }
    if(invalid) continue;
    if(cand[0] == 0) cand[0] = 1;
    if(!invalid && cand[0] > 0 && validstart(cand, base[0], base[1])) {
      if(bestcand.size() == 0 || smaller(cand, bestcand)) {
        bestcand.swap(cand);
      }
    }
    // check the prior
    if(base[0][len-3-nines] >= 0 && base[0][len-3-nines] < 9) break;
    if(base[1][len-3-nines] > 0) break;
  }
  if(bestcand.size()) {
    ret.swap(bestcand);
    ret.push_back(unitdigit / 10);
    ret.push_back(unitdigit % 10);
    return true;
  }
  return false;
}

void solve() {
  string s;
  cin >> s;
  // check everything up to 135
  string small = "";
  for(int i = 1; i <= 135; i++) small += to_string(i);
  for(int i = 0; i + s.size() <= small.size(); i++) {
    bool valid = true;
    for(int j = 0; valid && j < s.size(); j++) {
      if(s[j] == '?') continue;
      valid = s[j] == small[i+j];
    }
    if(valid) {
      cout << (i+1) << "\n";
      return;
    }
  }
  for(int len = 3; true; len++) {
    vector<int> ret;
    int cachedoffset = -1;
    for(int offset = 0; offset < len; offset++) {
      // do not carry
      vector<int> cand;
      for(int unit = 0; unit < 100; unit++) {
        if(checknocarry(len, offset, unit, s, cand)) {
          vector<array<int, 2>> curr;
          vector<int> base = cand;
          genvals(curr, cand, s.size() + offset);
          if(offset) curr.erase(curr.begin(), curr.begin() + offset); 
          if(cand.size() == len) {
            if(checkconsistency(s, curr)) {
              if(ret.size() == 0 || smaller(base, ret)) {
                ret = base;
                cachedoffset = offset;
              }
            }
          }
        }
      }
      // carry
      vector<int> base(len, 9);
      while(base[0] > 0) {
        vector<array<int, 2>> curr;
        vector<int> val = base;
        genvals(curr, val, s.size() + offset);
        if(offset) curr.erase(curr.begin(), curr.begin() + offset); 
        if(base.size() == val.size()) break;
        if(checkconsistency(s, curr)) {
          if(ret.size() == 0 || smaller(base, ret)) {
            ret = base;
            cachedoffset = offset;
          }
        }
        subtractone(base);
      }
    }
    if(ret.size()) {
      int64_t ans = 1;
      int64_t lhspow = 1;
      int64_t rhspow = 10;
      for(int x = 1; x < ret.size(); x++) {
        ans += (rhspow-lhspow+MOD)*x;
        ans %= MOD;
        rhspow = (rhspow*10)%MOD;
        lhspow = (lhspow*10)%MOD;
      }
      int64_t inc = 0;
      int64_t base = 1;
      for(int i = 0; i < ret.size(); i++) {
        inc = (10*inc+ret[i])%MOD;
        if(i) base = (10*base)%MOD;
      }
      ans += (inc-base+MOD) * len;
      ans %= MOD;
      ans += cachedoffset;
      ans %= MOD;
      if(ans < 0) ans += MOD;
      cout << ans << "\n";
      cout << flush;
      return;
    }
    assert(len <= s.size() + 2);
  }
}
int main() {
  int t;
  cin >> t;
  while(t--) solve();
}