#include <bits/stdc++.h>

using namespace std;

#ifdef zisk
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = [", _print(x)
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(x...) (void)0
template<class T> void pary(T l, T r) {}
#endif

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) ((long long)(v.size()))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng) // inclusive
#define cmax(a,b) (a = max(a,b))
#define cmin(a,b) (a = min(a,b))
typedef long long lll;
typedef long double ld;

/* TEMPLATE STARTS HERE */

/* TEMPLATE ENDS HERE */

__int128 pow10[37];

int get_length(__int128 x){
    if(x == 0) return 1;
    return upper_bound(pow10, pow10 + 37, x) - pow10;
}

int get_digit(pair<__int128, int> x){
    return (x.ff / pow10[get_length(x.ff) - 1 - x.ss]) % 10;
}
__int128 reverse_query_pos(pair<__int128, int> x){
    __int128 ans = 0;
    int dig = get_length(x.ff);
    for(int i = 1; i < dig; i++){
        ans += pow10[i-1] * i * 9;
    }
    x.ff -= pow10[dig-1];
    return ans + x.ff * dig + x.ss;
}

pair<__int128, int> query_pos(__int128 x){
    int dig = 1;
    while(x > 9 * pow10[dig - 1] * dig){
        x -= 9 * pow10[dig-1] * dig;
        dig++;
    }
    __int128 base = pow10[dig - 1];
    return {base + x / dig, x % dig};
}


int get_pos(__int128 x){
    return get_digit(query_pos(x));
}

bool match_pattern(string test, string pattern){
    if(siz(test) != siz(pattern)) return 0;
    for(int i = 0; i < siz(test); i++){
        if(pattern[i] == '.') continue;
        if(test[i] == ' ') return 0;
        if(test[i] != pattern[i] && pattern[i] != '?') return 0;
    }
    return 1;
}

bool test_ans(string s, __int128 ans){
    int n = siz(s);
    string ss;
    for(int i = 0; i < n; i++){
        ss.pb(get_pos(ans - 1 + i) + '0');
    }
    debug(ss, s);
    return match_pattern(ss, s);
}

// strings are all 0-based

string beg;
__int128 solve(){
    string s;
    cin >> s;
    int n = siz(s);

    __int128 ans = 1e36;
    
    // test if there's digit transition
    for(int i = 1; i < 30; i++){
        __int128 pos = reverse_query_pos({pow10[i], 0}); 
        string s2 (5 * n, ' ');
        for(int j = 0; j < 5 * n; j++){
            if(pos + j - 2 * n < 0) continue;
            s2[j] = get_pos(pos + j - 2 * n) + '0';
        }

        for(int j = 1; j < n; j++){
            // debug(j, s2.substr(2 * n - j, n), s);
            if(match_pattern(s2.substr(2 * n - j, n), s)){
                cmin(ans, pos - j + 1);
            }
        }
    }


    // now there's no digit transition

    // test short strings
    {
        for(int i = 0; i + n <= siz(beg); i++){
            if(match_pattern(beg.substr(i, n), s)){
                cmin(ans, (__int128) i + 1);
                break;
            }
        }
    }
    
    // test long strings
    for(int i = 3; i < 30; i++){
        for(int j = 0; j < i; j++){ // start on j-th digit of a number
            vector<string> numbers;
            {
                string cur = string(j, '.');
                for(char c : s){
                    cur.push_back(c);
                    if(siz(cur) == i){
                        numbers.push_back(cur);
                        cur = "";
                    }
                }
                if(siz(cur)){
                    while(siz(cur) < i) cur.push_back('.');
                    numbers.push_back(cur);
                }
            }

            // has no carry
            {
                bool good = 1;
                vector<int> start(i, 100);
                // one's digit
                {
                    for(int k = 0; k < siz(numbers); k++){
                        if(numbers[k].back() != '.' && numbers[k].back() != '?'){
                            if(start.back() == 100 || numbers[k].back() - '0' - k == start.back()){
                                start.back() = numbers[k].back() - '0' - k;
                            }else{
                                good = 0;
                            }
                        } 
                    }        
                }

                if(good && start.back() != 100){
                    if(start.back() + siz(numbers) > 10) good = 0;
                }
                // other digits
                {
                    for(int l = 0; l < i - 1; l++){
                        for(int k = 0; k < siz(numbers); k++){
                            if(numbers[k][l] != '.' && numbers[k][l] != '?'){
                                if(start[l] == 100 || start[l] == numbers[k][l] - '0'){
                                    start[l] = numbers[k][l] - '0';
                                }else{
                                    good = 0;
                                }
                            }
                        }
                    }
                }

                // can't have leading zeros
                if(start[0] == 0) good = 0;

                if(good){
                    __int128 val = 0;
                    if(start[0] == 100) start[0] = 1;

                    if(start[0] == 0) val = 10;
                    else val = start[0];
                    for(int l = 1; l < i; l++){
                        if(start[l] == 100) start[l] = 0;

                        val *= 10;
                        val += start[l];
                    }
                    if(ans > reverse_query_pos({val, j}) + 1 && test_ans(s, reverse_query_pos({val, j}) + 1)){
                        cmin(ans, reverse_query_pos({val, j}) + 1);
                    }
                }
            }
                
            // has carry
            {
                for(int k = 1; k < siz(numbers); k++){ // which number carries
                    for(int l = 1; l < i; l++){ // how many 9's were there
                        bool good = 1;
                        vector<int> start(i, 100);
                        for(int kk = 0; kk < l; kk++){
                            if(kk == 0) start[i - 1 - kk] = 10 - k;
                            else start[i - 1 - kk] = 9;
                        }
                        // one's digit
                        {
                            for(int kk = 0; kk < siz(numbers); kk++){
                                if(numbers[kk].back() != '.' && numbers[kk].back() != '?'){
                                    if(start.back() == 100 || (numbers[kk].back() - '0' - kk + 10) % 10 == start.back()){
                                        start.back() = (numbers[kk].back() - '0' - kk + 10) % 10;
                                    }else{
                                        good = 0;
                                    }
                                } 
                            }        
                        }
                        // other digits
                        {
                            for(int ll = 0; ll < i - 1; ll++){
                                for(int kk = 0; kk < siz(numbers); kk++){
                                    if(numbers[kk][ll] != '.' && numbers[kk][ll] != '?'){
                                        if(start[ll] == 100 || (numbers[kk][ll] - '0' - (kk >= k && ll == i - l - 1) + 10) % 10  == start[ll]){
                                            start[ll] = (numbers[kk][ll] - '0' - (kk >= k && ll == i - l - 1) + 10) % 10;
                                        }else{
                                            good = 0;
                                        }
                                    }
                                }
                            }
                        }
                        if(start[0] == 0) good = 0;

                        if(good){
                            __int128 val = 0;
                            if(start[0] == 100) start[0] = 1;

                            if(start[0] == 0) val = 10;
                            else val = start[0];
                            for(int ll = 1; ll < i; ll++){
                                if(start[ll] == 100) start[ll] = 0;

                                val *= 10;
                                val += start[ll];
                            }
                            if(ans > reverse_query_pos({val, j}) + 1 && test_ans(s, reverse_query_pos({val, j}) + 1)){
                                cmin(ans, reverse_query_pos({val, j}) + 1);
                            }
                        }
                    }
                }
            }
        }
    }
    assert(test_ans(s, ans));
    debug((lll)query_pos(ans - 1).ff, query_pos(ans - 1).ss);
    return ans;
}

signed main(){


    pow10[0] = 1;
    for(int i = 1; i < 37; i++){
        pow10[i] = pow10[i-1] * 10;
    }

    stringstream ss;
    for(int i = 1; i < 100; i++) ss << i;
    ss >> beg;

	cin.tie(0);
	ios_base::sync_with_stdio(false);


    int t;
    cin >> t;
    while(t--){
        auto x = solve();
        x %= 998244353;
        cout << lll(x) << endl;
    }
	return 0;
}