#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;

const int mod = 998244353;
int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    const __int128_t INF = 1e30;

    string t;
    for(int i = 1; i < 100000; i++){
        t += to_string(i);
    }

    auto check = [&](const string &t, const string &s){
        for(int i = 0; i + s.size() - 1 < t.size(); i++){
            bool ok = true;
            for(int j = 0; j < s.size(); j++){
                if (s[j] != '?' and s[j] != t[i + j]){
                    ok = false;
                    break;
                }
            }
            if (ok){
                return i;
            }
        }
        return -1;
    };

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

    auto i2s = [&](__int128_t x){
        string ans;
        while(x){
            ans.push_back(x % 10 + '0');
            x /= 10;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    };

    auto get = [&](__int128_t x){
        LL ans = 0;
        for(int i = 1; ; i++){
            if (x >= pow10[i]){
                ans += i * (pow10[i] - pow10[i - 1]) % mod;
            }
            else{
                ans += i * (x - pow10[i - 1] + 1) % mod;
                break;
            }
        }
        return ans % mod;
    };

    int T;
    cin >> T;
    while(T--){
        string s;
        cin >> s;
        const int n = s.size();
        int res = check(t, s);
        if (res != -1){
            cout << res + 1 << '\n';
            continue;
        }

        __int128_t ans = INF;
        
        // 在不同数位交界,即段内的数字可能位数不同
        for(int i = 5; i <= n + 1; i++){
            string s1, s2;
            __int128_t x = pow10[i - 1] - 1;
            for(; s1.size() < n; x -= 1){
                s1 = i2s(x) + s1;
            }
            __int128_t y = pow10[i - 1];
            for(; s2.size() < n; y += 1){
                s2 += i2s(y);
            }
            int pos = check(s1 + s2, s);
            if (pos != -1){
                ans = min(ans, x);
                // ans = min(ans, get(x) + pos + 1);
            }
        }

        auto update = [&](__int128_t val){
            ans = min(ans, val);
            // auto bk = val;
            // string ss;
            // while(ss.size() < 2 * n){
            //     ss += i2s(val);
            //     val += 1;
            // }
            // int pos = check(ss, s);
            // if (pos != -1){
            //     // ans = min(ans, get(bk - 1) + pos + 1);
            // }
        };

        // 段内每个数字位数都相同,注意到十位及以上最多变化一次
        // 每个数字位数为a
        // 偏移为b
        // 第一个数字个位为c
        // 进位的时候最后有d个9(不包含个位)
        auto solve = [&](int a, int b, int c){
            vector<string> v;
            if (b != 0){
                v.push_back(string(a - b, '?') + s.substr(0, b));
            }
            for(int i = b; i < n; i += a){
                v.push_back(s.substr(i, a));
            }
            if (!v.empty() and v.back().size() < a){
                v.back() += string(a - v.back().size(), '?');
            }
            int pos = v.size();
            for(int i = 0; i < v.size(); i++){
                if (i + c == 10) pos = i;
                int t = (c + i) % 10;
                if (v[i].back() != '?' and v[i].back() != char('0' + t)){
                    return;
                }
            }
            vector<int> state(a);
            for(int i = 0; i < a; i++){
                for(auto &str : v){
                    if (str[i] != '?'){
                        state[i] |= 1 << (str[i] - '0');
                    }
                }
            }
            if (pos == v.size()){
                __int128_t val = 0;
                for(int i = 0; i < a; i++){
                    if (__builtin_popcount(state[i]) >= 2) return;
                    if (i == 0){
                        if (state[i] == 0){
                            val = val * 10 + 1;
                        }
                        else{
                            int t = __lg(state[i]);
                            if (t == 0) return;
                            val = val * 10 + t;
                        }
                    }   
                    else if (i == a - 1){
                        val = val * 10 + c;
                    }
                    else{
                        if (state[i] == 0){
                            val = val * 10 + 0;
                        }
                        else{
                            val = val * 10 + __lg(state[i]);
                        }
                    } 
                }
                ans = min(ans, val);
                return;
            }
            __int128_t mn = INF;
            __int128_t cur = c;
            for(int d = 0; d + 1 < a; d++){
                bool ok = true;
                if (d != 0){
                    for(int j = 0; j < pos; j++){
                        if (v[j][a - 1 - d] != '?' and v[j][a - 1 - d] != '9'){
                            ok = false;
                            break;
                        }
                    }
                    if (!ok) break;
                    for(int j = pos; j < v.size(); j++){
                        if (v[j][a - 1 - d] != '?' and v[j][a - 1 - d] != '0'){
                            ok = false;
                            break;
                        }
                    }
                    if (!ok) break;
                    cur += pow10[d] * 9;
                }
                int s1 = 0, s2 = 0;
                for(int j = 0; j < pos; j++){
                    if (v[j][a - 1 - (d + 1)] != '?'){
                        s1 |= 1 << (v[j][a - 1 - (d + 1)] - '0');
                    }
                }
                for(int j = pos; j < v.size(); j++){
                    if (v[j][a - 1 - (d + 1)] != '?'){
                        s2 |= 1 << (v[j][a - 1 - (d + 1)] - '0');
                    }
                }
                int val = -1;
                if (__builtin_popcount(s1) >= 2 or __builtin_popcount(s2) >= 2) continue;
                if (s1 > 0 and s2 > 0){
                    int t1 = __lg(s1);
                    int t2 = __lg(s2);
                    if (t1 + 1 == t2){
                        val = t1;
                    }
                }
                else if (s1 > 0){
                    int t1 = __lg(s1);
                    if (d + 1 == a - 1){
                        if (t1 != 0 and t1 != 9){
                            val = t1;
                        }
                    }
                    else{
                        if (t1 != 9){
                            val = t1;
                        }
                    }
                }
                else if (s2 > 0){
                    int t2 = __lg(s2);
                    int t1 = t2 - 1;
                    if (d + 1 == a - 1){
                        if (t1 > 0){
                            val = t1;
                        }
                    }
                    else{
                        if (t1 >= 0){
                            val = t1;
                        }
                    }
                }
                else{
                    if (d + 1 == a - 1){
                        val = 1;
                    }
                    else{
                        val = 0;
                    }
                }
                if (val == -1) continue;
                __int128_t t = cur + val * pow10[d + 1];
                for(int j = 0; j + 1 < a - (d + 1); j++){
                    if (__builtin_popcount(state[j]) >= 2){
                        ok = false;
                        break;
                    }
                    if (j == 0){
                        if (state[j] == 0){
                            t = t + pow10[a - 1 - j];
                        }
                        else{
                            int k = __lg(state[j]);
                            if (k == 0){
                                ok = false;
                                break;
                            }
                            t = t + k * pow10[a - 1 - j];
                        }
                    }   
                    else{
                        if (state[j] == 0){

                        }
                        else{
                            t = t + __lg(state[j]) * pow10[a - 1 - j];
                        }
                    } 
                }
                if (ok){
                    mn = min(mn, t);
                }
            }
            update(mn);
        };

        for(int i = 5; i <= n + 1; i++){
            for(int j = 0; j < i; j++){
                for(int k = 0; k < 10; k++){
                    solve(i, j, k);
                }
            }
        }

        auto bk = ans;
        string ss;
        while(ss.size() < 10 * n){
            ss += i2s(ans);
            ans += 1;
        }
        int pos = check(ss, s);
        cout << (get(bk) + pos + 1) % mod << '\n';
    }

}