/**
 * @author n685
 * @brief
 * @date 2024-10-12 11:22:13
 *
 *
 */
#include "bits/stdc++.h"

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbg_proj(...) 420
#define dbg_rproj(...) 420420
void nline() {}
void bar() {}
void start_clock() {}
void end_clock() {}
#endif

using i128 = __int128_t;
template <class T> constexpr T INF = T{};
template <> constexpr int INF<int> = 0x3f3f3f3f;                 // 1061109567
template <> constexpr int64_t INF<int64_t> = 0x3f3f3f3f3f3f3f3f; // 4557430888798830399
template <>
constexpr i128 INF<i128>
    = i128{INF<int64_t>} << 64 | INF<int64_t>; // 84069761239290679208598432424319205183

constexpr int MOD = 998'244'353;
constexpr int MXLG = 25;
constexpr std::array<i128, MXLG + 1> p10 = []() {
    std::array<i128, MXLG + 1> ans{};
    ans[0] = 1;
    for (int i = 1; i <= MXLG; ++i) {
        ans[i] = ans[i - 1] * 10;
    }
    return ans;
}();
int log10(i128 val) {
    for (int i = 0; i <= MXLG; ++i) {
        if (val < p10[i]) {
            return i - 1;
        }
    }
    return MXLG;
}

i128 pos(i128 val) {
    int lg = log10(val);
    i128 ans = 0;
    for (int i = lg; i >= 0; --i) {
        ans += (i + 1) * (val - p10[i] + 1);
        val = p10[i] - 1;
    }
    return ans;
}
std::string to_string(i128 val) {
    if (val <= std::numeric_limits<uint64_t>::max()) {
        return std::to_string(static_cast<uint64_t>(val));
    }
    std::string ans;
    while (val > 0) {
        ans += static_cast<char>('0' + val % 10);
        val /= 10;
    }
    std::reverse(ans.begin(), ans.end());
    return ans;
}
i128 stoi128(const std::string& s) {
    i128 ans = 0;
    for (char c : s) {
        assert(c != '?');
        ans = 10 * ans + (c - '0');
    }
    return ans;
}

bool match(const std::string& s, const std::string& ls) {
    int n = static_cast<int>(s.size());
    for (int i = 0; i < n; ++i) {
        if (s[i] != '?' && ls[i] != '?' && s[i] != ls[i]) {
            return false;
        }
    }
    return true;
}

constexpr int MX = 100000;
void solve() {
    std::string s;
    std::cin >> s;
    int n = static_cast<int>(s.size());
    i128 ans = INF<i128>;

    // starts from 1..10^5
    for (i128 i = 1; i <= MX; ++i) {
        int lg = log10(i);
        for (int st = -lg; st <= 0; ++st) {
            std::string ls;
            for (i128 val = i; static_cast<int>(ls.size()) + st < n; ++val) {
                ls += to_string(val);
            }
            if (match(s, ls.substr(-st))) {
                ans = std::min(ans, pos(i - 1) + 1 - st);
            }
        }
    }

    // includes power of 10
    for (int lg = 5; lg <= MXLG; ++lg) {
        for (int p = -lg; p < n; ++p) {
            int st = p;
            i128 fi = p10[lg];
            while (st > 0) {
                st -= lg;
                --fi;
            }
            std::string ls;
            for (i128 val = fi; static_cast<int>(ls.size()) + st < n; ++val) {
                ls += to_string(val);
            }
            if (match(s, ls.substr(-st))) {
                ans = std::min(ans, pos(fi - 1) + 1 - st);
            }
        }
    }

    // one number
    {
        std::string ls = s;
        for (int i = 1; i < static_cast<int>(ls.size()); ++i) {
            if (ls[i] == '?') {
                ls[i] = '0';
            }
        }
        int off = 0;
        if (ls[0] == '0') {
            ++off;
            ls.insert(ls.begin(), '1');
        } else if (ls[0] == '?') {
            ls[0] = '1';
        }
        ans = std::min(ans, pos(stoi128(ls) - 1) + off + 1);
    }

    // no carry
    for (int lg = 5; lg <= MXLG; ++lg) {
        int wi = lg + 1;
        for (int pl = 0; pl < wi; ++pl) {
            int pr = (wi - (n + pl) % wi) % wi;
            int sz = n + pr;
            std::string ss = std::string(pl, '?') + s + std::string(pr, '?');
            std::string ls(wi, '?');
            bool g = true;
            for (int i = 0; i < sz; i += wi) {
                for (int j = 0; j < wi; ++j) {
                    if (ss[i + j] == '?') {
                        continue;
                    }
                    if (j == wi - 1) {
                        int dv = ss[i + j] - '0';
                        if (dv < i / wi || (ls[j] != '?' && ls[j] - '0' != dv - i / wi)
                            || dv + (sz - i) / wi - 1 >= 10)
                        {
                            g = false;
                            break;
                        }
                        ls[j] = static_cast<char>(dv - i / wi + '0');
                    } else {
                        int dv = ss[i + j] - '0';
                        if ((j == 0 && dv == 0) || (ls[j] != '?' && ls[j] != ss[i + j])) {
                            g = false;
                            break;
                        }
                        ls[j] = ss[i + j];
                    }
                }
            }
            if (g && ls[0] != '0') {
                if (ls[0] == '?') {
                    ls[0] = '1';
                }
                for (int i = 1; i < wi; ++i) {
                    if (ls[i] == '?') {
                        ls[i] = '0';
                    }
                }
                ans = std::min(ans, pos(stoi128(ls) - 1) + pl + 1);
            }
        }
    }

    // carry
    for (int lg = 5; lg <= MXLG; ++lg) {
        int wi = lg + 1;
        for (int pl = 0; pl < wi; ++pl) {
            int pr = (wi - (n + pl) % wi) % wi;
            int sz = n + pr;
            std::string ss = std::string(pl, '?') + s + std::string(pr, '?');
            for (int cpos = wi; cpos < sz; cpos += wi) {
                for (int cw = 1; cw < wi; ++cw) {
                    std::string ls(wi, '?');
                    ls[wi - 1] = static_cast<char>(10 - cpos / wi + '0');
                    for (int i = wi - cw; i < wi - 1; ++i) {
                        ls[i] = '9';
                    }
                    bool g = true;
                    for (int i = 0; i < cpos; i += wi) {
                        for (int j = 0; j < wi; ++j) {
                            if (ss[i + j] == '?') {
                                continue;
                            }
                            if (j == wi - 1) {
                                int dv = ss[i + j] - '0';
                                if (dv < i / wi || (ls[j] != '?' && ls[j] - '0' != dv - i / wi)) {
                                    g = false;
                                    break;
                                }
                                ls[j] = static_cast<char>(dv - i / wi + '0');
                            } else {
                                int dv = ss[i + j] - '0';
                                if (j >= wi - cw && dv != 9) {
                                    g = false;
                                    break;
                                }
                                if (j == wi - cw - 1 && dv == 9) {
                                    g = false;
                                    break;
                                }
                                if ((j == 0 && dv == 0) || (ls[j] != '?' && ls[j] != ss[i + j])) {
                                    g = false;
                                    break;
                                }
                                ls[j] = ss[i + j];
                            }
                        }
                    }
                    if (!g) {
                        continue;
                    }
                    for (int i = cpos; i < sz; i += wi) {
                        for (int j = 0; j < wi; ++j) {
                            if (ss[i + j] == '?') {
                                continue;
                            }
                            if (j == wi - 1) {
                                int dv = ss[i + j] - '0';
                                int od = dv - i / wi + 10;
                                if (ls[j] - '0' != od) {
                                    g = false;
                                    break;
                                }
                                ls[j] = static_cast<char>(od + '0');
                            } else {
                                int dv = ss[i + j] - '0';
                                if (j >= wi - cw) {
                                    if (dv != 0) {
                                        g = false;
                                        break;
                                    }
                                    dv = 9;
                                } else if (j == wi - cw - 1) {
                                    if (dv == 0) {
                                        g = false;
                                        break;
                                    }
                                    --dv;
                                }
                                if ((j == 0 && dv == 0) || (ls[j] != '?' && ls[j] != dv + '0')) {
                                    g = false;
                                    break;
                                }
                                ls[j] = static_cast<char>(dv + '0');
                            }
                        }
                    }
                    if (g && ls[0] != '0') {
                        if (ls[0] == '?') {
                            ls[0] = '1';
                        }
                        for (int i = 1; i < wi - cw; ++i) {
                            if (ls[i] == '?') {
                                ls[i] = '0';
                            }
                        }
                        ans = std::min(ans, pos(stoi128(ls) - 1) + pl + 1);
                    }
                }
            }
        }
    }

    dbg(to_string(ans));
#ifdef LOCAL
    i128 l = 1, r = static_cast<i128>(2e25);
    while (l < r) {
        i128 mid = l + (r - l) / 2;
        if (pos(mid) + 1 >= ans) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    dbg(to_string(l));
#endif
    std::cout << static_cast<int>(ans % MOD) << '\n';
}

int main() {
#ifndef LOCAL
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
#endif

    int t;
    std::cin >> t;
    for (int i = 0; i < t; ++i) {
        dbg(i + 1);
        solve();
        bar();
    }
}