#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
vector<__int128_t> TEN;
string to_string(__int128_t A){
  string ans;
  while (A != 0){
    ans += '0' + (int) (A % 10);
    A /= 10;
  }
  reverse(ans.begin(), ans.end());
  return ans;
}
__int128_t get(__int128_t A){
  string S = to_string(A);
  int N = S.size();
  __int128_t ans = 0;
  for (int i = 1; i < N; i++){
    ans += (TEN[i] - TEN[i - 1]) * i;
  }
  ans += (A - TEN[N - 1]) * N;
  return ans;
}
int main(){
  TEN.resize(31);
  TEN[0] = 1;
  for (int i = 0; i < 30; i++){
    TEN[i + 1] = TEN[i] * 10;
  }
  int t;
  cin >> t;
  string C;
  for (int i = 1; i <= 1010; i++){
    C += to_string(i);
  }
  int C_LEN = C.size();
  __int128_t INF = TEN[30];
  for (int i = 0; i < t; i++){
    string s;
    cin >> s;
    int N = s.size();
    __int128_t ans = INF;
    for (int j = 0; j <= C_LEN - N; j++){
      bool ok = true;
      for (int k = 0; k < N; k++){
        if (C[j + k] != s[k] && s[k] != '?'){
          ok = false;
        }
      }
      if (ok){
        ans = min(ans, (__int128_t) j);
      }
    }
    for (int j = 4; j <= N + 1; j++){
      for (int k = 0; k < j; k++){
        vector<int> idx = {-k};
        while (idx.back() < N){
          int a = idx.back() + j;
          idx.push_back(a);
        }
        int cnt = idx.size() - 1;
        vector<int> d(j, -1);
        bool no_carry_ok = true;
        for (int l = 0; l < cnt; l++){
          for (int m = 0; m < j; m++){
            int p = idx[l] + m;
            if (0 <= p && p < N){
              if (s[p] != '?'){
                if (m != j - 1){
                  if (d[m] == -1){
                    d[m] = s[p] - '0';
                  } else if (d[m] != s[p] - '0'){
                    no_carry_ok = false;
                  }
                } else {
                  if (d[m] == -1){
                    if (s[p] - '0' - l < 0 || s[p] - '0' - l > 10 - cnt){
                      no_carry_ok = false;
                    } else {
                      d[m] = s[p] - '0' - l;
                    }
                  } else if (d[m] != s[p] - '0' - l){
                    no_carry_ok = false;
                  }
                }
              }
            }
          }
        }
        if (d[0] == 0){
          no_carry_ok = false;
        }
        if (no_carry_ok){
          if (d[0] == -1){
            d[0] = 1;
          }
          for (int l = 1; l < j; l++){
            if (d[l] == -1){
              d[l] = 0;
            }
          }
          __int128_t A = 0;
          for (int l = 0; l < j; l++){
            A *= 10;
            A += d[l];
          }
          ans = min(ans, get(A) + k);
        }
        for (int l = 1; l < cnt; l++){
          for (int m = 0; m < j; m++){
            bool ok = true;
            vector<int> d(j, -1);
            for (int n = j - m; n < j - 1; n++){
              d[n] = 9;
            }
            d[j - 1] = 10 - l;
            for (int n = 0; n < cnt; n++){
              for (int o = 0; o < j; o++){
                int p = idx[n] + o;
                if (0 <= p && p < N){
                  if (s[p] != '?'){
                    if (o < j - m - 1){
                      if (d[o] == -1){
                        d[o] = s[p] - '0';
                      } else if (d[o] != s[p] - '0'){
                        ok = false;
                      }
                    } else if (o == j - m - 1){
                      if (d[o] == -1){
                        if (n < l){
                          if (s[p] - '0' == 9){
                            ok = false;
                          } else {
                            d[o] = s[p] - '0';
                          }
                        } else {
                          if (s[p] - '0' == 0){
                            ok = false;
                          } else {
                            d[o] = s[p] - '0' - 1;
                          }
                        }
                      } else if (n < l && d[o] != s[p] - '0' || n >= l && d[o] != s[p] - '0' - 1){
                        ok = false;
                      }
                    } else if (o < j - 1){
                      if (n < l && s[p] - '0' != 9){
                        ok = false;
                      }
                      if (n >= l && s[p] - '0' != 0){
                        ok = false;
                      }
                    } else {
                      if (s[p] - '0' != (10 - l + n) % 10){
                        ok = false;
                      }
                    }
                  }
                }
              }
            }
            if (d[0] == 0){
              ok = false;
            }
            if (ok){
              if (d[0] == -1){
                d[0] = 1;
              }
              for (int n = 1; n < j; n++){
                if (d[n] == -1){
                  d[n] = 0;
                }
              }
              __int128_t A = 0;
              for (int n = 0; n < j; n++){
                A *= 10;
                A += d[n];
              }
              ans = min(ans, get(A) + k);
            }
          }
        }
        for (int l = 1; k - j + (l - 1) * j < N; l++){
          __int128_t A = TEN[j] - l;
          __int128_t A2 = A;
          string S;
          S += to_string(A2).substr(k);
          while (S.size() < N){
            A2++;
            S += to_string(A2);
          }
          bool ok = true;
          for (int m = 0; m < N; m++){
            if (S[m] != s[m] && s[m] != '?'){
              ok = false;
            }
          }
          if (ok){
            ans = min(ans, get(A) + k);
          }
        }
      }
    }
    ans++;
    cout << (long long) (ans % MOD) << endl;
  }
}