#include <iostream>
#include <string>
#include <vector>

using ll = long long ;
using namespace std ;
string s ;
const int SIZ = 8192 ;
char wbuf[SIZ] ;
const ll MOD = 998244353 ;
int checkit(const string &s, const char *p, int len) {
   for (int i=0; i<len; i++)
      if (s[i] != '?' && s[i] != p[i])
         return 0 ;
   return 1 ;
}
ll champof(const string &s) {
   ll r = 1 ;
   ll cnt = 9 ;
   for (int i=1; i<(int)s.size(); i++) {
      r = (r + i * cnt) % MOD ;
      cnt = cnt * 10 % MOD ;
   }
   ll addme = 0 ;
   int bias = 1 ;
   for (auto c: s) {
      addme = (10 * addme + c - bias) % MOD ;
      bias = 0 ;
   }
   return (s.size() * addme + r) % MOD ;
}
void dotest() {
   string cand ;
   pair<string, ll> sol ;
   cin >> s ;
   int slen = s.size() ;
   int len = 1 ;
   ll val = 1 ;
   ll np10 = 10 ;
   ll lpos = 1 ;
   int pos = 0 ;
   while (1) {
      while (pos + len + 1 < SIZ) {
         snprintf(wbuf+pos, len+1, "%lld", val) ;
         val++ ;
         pos += len ;
         if (val == np10) {
            len++ ;
            np10 *= 10 ;
         }
      }
      int cpos = 0 ;
      while (cpos + slen <= pos) {
         if (checkit(s, wbuf + cpos, slen)) {
            cout << lpos + cpos << endl ;
            return ;
         }
         cpos++ ;
      }
      lpos += cpos ;
      for (int i=0; i+cpos < pos; i++)
         wbuf[i] = wbuf[cpos+i] ;
      pos = pos - cpos ;
      if (val > 11000) // need at least four digits
         break ;
   }
   for (int dig=4; dig<slen+2; dig++) {
      int before = slen / (dig - 1) + 1 ;
      int pos = 0 ;
      for (int d=-before; d<=before; d++) {
         if (d < 0) {
            for (int i=0; i+1<dig; i++)
               wbuf[pos++] = '9' ;
            wbuf[pos-1] -= (-1-d) % 10 ;
            wbuf[pos-2] -= (-1-d) / 10 ;
         } else {
            wbuf[pos++] = '1' ;
            for (int i=0; i+1<dig; i++)
               wbuf[pos++] = '0' ;
            wbuf[pos-1] += d % 10 ;
            wbuf[pos-2] += d / 10 ;
         }
      }
      wbuf[pos] = 0 ;
      int cpos = 0 ;
      while (cpos + slen <= pos) {
         if (checkit(s, wbuf + cpos, slen)) {
            string str ;
            for (int i=0; i+1<dig; i++)
               str.push_back(wbuf[i]-'0') ;
            ll r = (champof(str) + cpos) % MOD ;
            cout << r << endl ;
            return ;
         }
         cpos++ ;
      }
      for (int spos=0; spos<dig; spos++) {
         int cpos = spos ;
         int addend = 0 ;
         vector<vector<pair<int, int>>> req(dig) ;
         vector<int> digsseen(dig) ;
         int maxadd = 0 ;
         for (int i=0; i<slen; i++) {
            if (s[i] != '?') {
               req[cpos].push_back({addend, s[i]-'0'}) ;
               digsseen[cpos] |= 1<<(s[i]-'0') ;
               maxadd = addend ;
            }
            cpos-- ;
            if (cpos < 0) {
               cpos = dig - 1 ;
               addend++ ;
            }
         }
         if (digsseen[dig-1] & (1 << 0)) // can't have a leading zero
            continue ;
         int base = -1 ;
         if (req[0].size() > 1) {
            base = (req[0][0].second - req[0][0].first + 1000) % 10 ;
            int good = 1 ;
            for (int i=1; good && i<(int)req[0].size(); i++)
               if ((req[0][i].second - req[0][i].first + 1000) % 10 != base)
                  good = 0 ;
            if (good == 0)
               continue ;
         }
         int hidiff = dig-1 ;
         while (hidiff >= 0 && (digsseen[hidiff] & (digsseen[hidiff]-1)) == 0)
            hidiff-- ;
            if (hidiff >= 2 && digsseen[hidiff] != 513 && digsseen[hidiff] != (digsseen[hidiff] & - digsseen[hidiff]) * 3)
              continue ;
        for (; hidiff < dig; hidiff++) {
         int newsol = 0 ;
         int start = 0 ;
         int inc = 1 ;
         if (base >= 0) {
            start = base ;
            inc = 10 ;
         }
         for (int low2=start; low2<100; low2 += inc) {
            int ok = 1 ;
            int dv = 1 ;
            int rollover = 100 - low2 ;
            for (int i=0; ok && i<2; i++) {
               for (auto v: req[i]) {
                  int valat = low2 + v.first ;
                  if (valat / dv % 10 != v.second) {
                     ok = 0 ;
                     break ;
                  }
               }
               dv *= 10 ;
            }
            if (!ok)
               continue ;
            int t = low2 ;
            for (int i=0; i<2; i++) {
               wbuf[i] = t % 10 ;
               t /= 10 ;
            }
            for (int i=2; ok && i<dig; i++) {
               wbuf[i] = 100 ;
               for (auto v: req[i]) {
                  int need = -1 ;
                  if (v.first < rollover)
                     need = v.second ;
                  else if (v.second > 0)
                     need = v.second - 1 ;
                  else
                     need = 9 ;
                  if (wbuf[i] == 100) {
                     wbuf[i] = need ;
                  } else if (wbuf[i] != need) {
                     ok = 0 ;
                  }
               }
               if (wbuf[i] == 100) {
                  if (i < hidiff) {
                     wbuf[i] = 9 ;
                  } else if (i == dig-1) {
                     wbuf[i] = 1 ;
                  } else {
                     wbuf[i] = 0 ;
                  }
               }
               if (wbuf[i] < 9)
                  rollover = 1000 ;
            }
            if (rollover > maxadd && ok && wbuf[dig-1] > 0) {
               newsol = 1 ;
               cand.clear() ;
               for (int i=0; i<dig; i++)
                  cand.push_back(wbuf[dig-1-i]) ;
               if (sol.first.size() == 0 || sol.first >= cand) {
                  ll res = champof(cand) + (dig - 1 - spos) ;
                  if (sol.first.size() == 0 || sol.first > cand || (sol.first == cand && res < sol.second))
                     sol = {cand, res} ;
               }
            }
         }
         if (newsol == 0)
            break ;
       }
      }
      if (sol.first.size()) {
         ll low = sol.second ;
         cout << (low % 998244353) << endl ;
         return ;
      }
   }
}
int main() {
   int T ;
   cin >> T ;
   for (int i=0; i<T; i++)
      dotest() ;
}