#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int mod = 998244353;
string s;
__int128 num;
int pos;
void upd(__int128 nm , int p) {
    if(num == -1 || nm < num) {
        num = nm ; pos = p;
    }
    else if(num == nm) {
        pos = min(pos , p);
    }
    return ;
}
string to_str(__int128 x , int len = 0) {
    string ans ;
    while(x) {
        ans += ((int)(x % 10) + '0') ;
        x /= 10;
    }
    while(ans.size() < len) ans += "0" ;
    reverse(ans.begin() , ans.end()) ;
    return ans;
}
int get_mat(const string& a,const string& b) {
    // cout <<b << '\n';
    for(int i = 0;i + b.size() - 1 < a.size();i++) {
        bool f = 1;
        for(int j = 0;j < b.size();j++) {
            if(!(b[j] == '?' || (b[j] == a[i + j ]))) {
                f = 0 ; break ;
            }
        }
        if(f) return i;
    }
    return -1;
}
int sump(__int128 x) {
    
    string w = to_str(x) ;
    // cout << w << '\n';
    int ans = 0;
    int pw[30] = {0} ;
    pw[0] = 1;
    for(int i = 1;i <= 29;i++) pw[i] = 10LL * pw[i - 1] % mod;
    for(int l = 1 ; l < w.size() ; l++) {
        ans = (ans + 1LL * l * (pw[l] - pw[l - 1] + mod)) % mod;
    }
    for(int i = 0;i < w.size();i++) {
        int len = w.size() - i - 1;
        if(i == 0) ans = (ans + 1LL * w.size() * (w[i] - '0' - 1) * pw[len]) % mod;
        else ans = (ans + 1LL * w.size() * (w[i] - '0') * pw[len]) % mod;
    }
    return ans;
}
__int128 to_int(string s) {
    __int128 ans = 0;
    for(int i = 0;i < s.size();i++) ans = (ans * 10 + s[i] - '0') ;
    return ans;
}
void solv() {
    cin >> s;
    string ss = "1" + s;
    for(auto &x : ss) x = (x == '?' ? '0' : x) ;
    num = to_int(ss); pos = 1;

    for(int l = 1;l <= s.size();l++) {
        ///
        __int128 k = 0;
        for(int j = 0;j < l;j++) k = k * 10 + 9;
        string cur ;
        int d = (s.size() / l + 1) ;
        for(__int128 x = k - d; x <= k + d ; x++) {
            if(x < 0) continue ;
            cur += to_str(x) ;
        }
        // cout << "TEST " << cur <<' ' << s << '\n';
        int pos = get_mat(cur , s) ;
        // cout << pos << '\n';
        if(pos != -1) {
            int curp = 0;
            for(__int128 x = k - d; x <= k + d ; x++) {
                if(x < 0) continue ;
                int len ;
                if(x <= k) len = l ;
                else len = l + 1;
                if(curp + len <= pos) {curp += len ; continue ;}
                else {
                    upd(x , pos - curp) ;break ;
                }
            }
        }
        for(int j = 0;j < l;j++) {
            vector<string> vec ;
            string w ; for(int x = 0 ; x < j;x++) w += "?" ;
            for(int x = 0;x < s.size();x++) {
                w += s[x] ;
                if(w.size() == l) {
                    vec.push_back(w) ; w = "" ;
                }
            }
            if(w.size()) {
                while(w.size() < l) w += "?" ;
                vec.push_back(w);
            }
            for(int k = l - 1 ; k >= 0;k--) {
                bool f = 1;
                string fir ;
                for(int a = 0 ; a < l;a++) fir += '?' ;
                for(auto &s : vec) {
                    for(int p = 0 ; p < k;p++) {
                        if(s[p] != '?') {
                            if(fir[p] == '?') fir[p] = s[p];
                            else if(fir[p] != s[p]) {f = 0 ; break ;}
                        }
                    }
                    if(!f) break ;
                }
                if(!f) continue ;
                __int128 head = 0;

                for(int p = 0;p < k;p++) {
                    if(fir[p] == '?') {
                        if(p == 0) fir[p] = '1' ;
                        else fir[p] = '0' ;
                    }
                    head = head * 10 + fir[p] - '0' ;
                    if(p == 0 && fir[p] == '0') f = 0;
                }
                if(!f) continue ;

                for(int p = k ; p < l;p++) head = head * 10 ;

                __int128 a9 = 0 , lv , upper , bg;
                for(int p = 0 ; p < l - k - 1 ; p++) a9 = a9 * 10 + 9;
                upper = a9 * 10 + 9; 
                for(__int128 lst = a9 - vec.size() ; lst <= a9 ; lst++) {
                    if(lst < 0) continue ;
                    for(int d = 0 ; d < 9;d++) { /// k这一位
                        if(k == 0 && d == 0) continue ;

                        lv = d * (a9 + 1) + lst ;
                        bg = lv + head;
                        bool f = 1;
                        for(auto &s : vec) {
                            if(lv > upper) {f = 0 ; break ;}
                            string w = to_str(lv , l - k) ;
                            for(int p = k ; p < l ; p++) {
                                if(!(s[p] == '?' || s[p] == w[p - k])) {
                            // if(l == 7 && j == 0 && bg == 1309997) {
                            //     cout << "Bad Mat " << s <<' ' << w << '\n';
                            //     cout << to_str(a9) <<' ' << to_str(lst) <<' ' << to_str(lv) <<' ' << d << '\n';
                            //     cout << "k = " << k << '\n';
                            // }
                                    f = 0 ; break ;
                                }
                            }
                            if(!f) break ;
                            lv++ ;
                        }
                        if(!f) continue ;
                        // if(bg == 0) {
                        // cout << "on " << l <<' ' << k <<' ' << to_str(bg) << '\n';
                        // for(auto s : vec) cout << s << '\n';
                        // }
                        upd(bg , j) ;
                    }
                }
                
            }
        }
    }
    int ans = (sump(num ) + pos + 1 ) % mod;
    // cout << to_str(num) << ' ' << pos << '\n';
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false) ; cin.tie(0) ; 
    int t ; cin >> t;
    while(t--) solv() ;
    return 0;
}