#include <bits/stdc++.h>
const char nl = '\n';
using namespace std;
using ll = long long;
using ld = long double;
const int MOD = 998'244'353;
const __int128 INF = 1e30;

string to_string(__int128 x) {
  string ret;
  assert(x > 0);
  while (x) {
    ret.push_back('0'+x%10);
    x /= 10;
  }
  reverse(begin(ret), end(ret));
  return ret;
}

__int128 stolll(string s) {
  __int128 x = 0;
  //cerr << s << nl;
  for (char c : s) {
    x = x * 10 + (c - '0');
    //cerr << "x: " << ll(x) << " " << int(c-'0') << nl;
  }
  //cerr << s << " " << ll(x) << nl;
  return x;
}

void solve() {
  string s; cin >> s;
  string champ;
  for (int i = 1; i <= 1000; i++) {
    champ += to_string(i);
  }
  //cerr << champ.size() << nl;
  for (int i = 0; i < champ.size(); i++) {
    bool bad = 0;
    for (int j = 0; j < s.size(); j++) {
      if (i+j >= champ.size() || (s[j] != '?' && s[j] != champ[i+j])) {
        bad = 1;
        break;
      }
    }
    if (!bad) {
      cout << i+1 << nl;
      return;
    }
  }
  __int128 ans = INF;
  for (__int128 pw = 1000, lg = 3; lg <= 26; lg++, pw *= 10) {
    string cur;
    for (__int128 i = pw-10; i < pw+10; i++) cur += to_string(i);
    for (int i = 0; i < cur.size(); i++) {
      bool bad = 0;
      for (int j = 0; j < s.size(); j++) {
        if (i+j >= cur.size() || (s[j] != '?' && s[j] != cur[i+j])) {
          bad = 1;
          break;
        }
      }
      if (!bad) {
        __int128 off = 0;
        for (__int128 j = 0, pw = 1; j < lg; j++, pw *= 10) {
          off += 9*pw*(j+1);
        }
        off -= 10*lg;
        ans = min(ans, off + i + 1);
      }
    }
  }
  for (int dig = 4; dig <= 25; dig++) {
    for (int off = 0; off < dig; off++) {
      for (int nine = 0; nine < dig-2; nine++) {
        for (int last = 0; last < 100; last++) {
          string t(dig, '?');
          t[t.size()-1] = '0' + (last % 10);
          t[t.size()-2] = '0' + (last / 10);
          for (int i = 0; i < nine; i++) {
            t[t.size()-3-i] = '9';
          }
          __int128 curlast = last;
          __int128 pw = 100;
          for (__int128 i = 0; i < nine; i++, pw *= 10) {
            curlast += 9*pw;
          }
          //if (dig == 4 && off == 2 && nine == 0 && last == 13) cerr << "!\n";
          bool bad = 0;
          //cerr << nine << " " << ll(curlast) << " " << ll(pw) << nl; return;
          //if (dig == 4 && off == 1 && nine == 0 && last == 0) cerr << s[i+j] << " " << j << nl;
          for (int i = -off; i < int(s.size()); i += dig, curlast++) {
            for (int j = 0; j < dig; j++) {
              if (i+j < 0 || i+j >= s.size()) continue;
              //if (dig == 4 && off == 1 && nine == 0 && last == 0) cerr << s[i+j] << " " << j << nl;
              if (s[i+j] == '?') continue;
              if (j >= dig-nine-2) {
                // must match curlast
                __int128 curdig = curlast;
                for (int k = 0; k < dig-j-1; k++) curdig /= 10;
                if (curdig%10 != s[i+j]-'0') {
                  //if (dig == 4 && off == 2 && nine == 0 && last == 13) cerr << "! " << int(dig%10) << " " << s[i+j] << nl;
                  bad = 1;
                  break;
                }
              } else {
                // must match other digs
                if (j == dig-nine-3 && curlast >= pw && s[i+j] == '0') {
                  //if (dig == 4 && off == 2 && nine == 0 && last == 13) cerr << "!! " << ll(curlast) << " " << s[i+j] << nl;
                  bad = 1;
                  break;
                }
                if (t[j] == '?') {
                  t[j] = s[i+j] - (j == dig-nine-3 && curlast >= pw);
                } else if (t[j] != s[i+j] - (j == dig-nine-3 && curlast >= pw)) {
                  //if (dig == 4 && off == 2 && nine == 0 && last == 13) cerr << "!!! " << ll(curlast) << " " << s[i+j] << " " << t[j] << nl;
                  bad = 1;
                  break;
                }
              }
            }
          }
          //if (dig == 4 && off == 2 && nine == 0 && last == 13) cerr << bad << " " << t << nl;
          if (!bad) {
            __int128 ind = 0;
            if (t[0] == '?') t[0] = '1';
            for (char& c : t) {
              if (c == '?') c = '0';
            }
            //cerr << "good " << t << nl; return;
            if (t[0] != '0') {
              __int128 x = stolll(t);
              __int128 pw = 1;
              for (__int128 j = 0; j < dig-1; j++, pw *= 10) {
                ind += 9*pw*(j+1);
              }
              //if (dig == 4) cerr << ll(ind) << " " << ll(x) << " " << ll(pw) << nl;
              //cerr << t << " -> " << ll(x) << nl;
              ind += dig*(x - pw);
              ind += off + 1;
              //if (ind < ans) cerr << dig << " " << off << " " << nine << " " << last << " " << t << nl;
              ans = min(ans, ind);
            }
          }
        }
      }
    }
  }
  cout << ll(ans % MOD) << nl;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  // - <= 2 digits (easy)
  // - power of 10 exists in substring (easy)
  // - iterate over:
  //   - # digits
  //   - pos
  //   - carry
  //   - last digit(s)
  int T; cin >> T;
  while (T--) solve();
}