// cf bits/extc++.h nonsense
#ifdef ONLINE_JUDGE
#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
#endif

#line 1 "b.cpp"
// 69683a8183e36171b0123a3fbef815656276c8d9
#include "bits/extc++.h"
#line 1 "/home/skittles1412/workspace/cp/library/template.hpp"



#line 5 "/home/skittles1412/workspace/cp/library/template.hpp"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

using u32 = uint32_t;
using u64 = uint64_t;
using ld = long double;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))


#line 1 "/home/skittles1412/workspace/cp/library/utils.hpp"



#line 5 "/home/skittles1412/workspace/cp/library/utils.hpp"

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
    out << "[";
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << ", ";
        }
        out << arr[i];
    }
    return out << "]";
}

template <typename T, size_t N>
ostream& operator<<(ostream& out, const array<T, N>& arr) {
    out << "[";
    for (size_t i = 0; i < N; i++) {
        if (i) {
            out << ", ";
        }
        out << arr[i];
    }
    return out << "]";
}

template <typename A, typename B>
ostream& operator<<(ostream& out, const pair<A, B>& p) {
    return out << "(" << p.first << ", " << p.second << ")";
}

/**
 * Computes the first x in [l, r) such that cb(x) is true.
 *
 * If no x in that range is true, returns r
 */
template <typename T, typename Cb>
T first_true(T l, T r, const Cb& cb) {
    while (l < r) {
        T mid = (l + r) / 2;
        if (cb(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

/**
 * Computes the last x in (l, r] such that cb(x) is true.
 *
 * If no x in that range is true, returns l
 */
template <typename T, typename Cb>
T last_true(T l, T r, const Cb& cb) {
    while (l < r) {
        T mid = (l + r + 1) / 2;
        if (cb(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l;
}

template <typename T>
T reversed(T arr) {
    reverse(begin(arr), end(arr));
    return arr;
}

template <typename T>
bool is_palin(const T& arr) {
    return arr == reversed(arr);
}

template <typename T>
T sorted(T arr) {
    sort(begin(arr), end(arr));
    return arr;
}

template <typename T>
T negated(T arr) {
    for (auto& a : arr) {
        a = -a;
    }
    return arr;
}

template <typename T, bool STRICT>
vector<int> comp_prev_helper(const vector<T>& arr) {
    int n = sz(arr);

    vector<int> ans(n);

    vector<pair<int, int>> st;
    for (int i = 0; i < n; i++) {
        auto cmp = [&]() -> bool {
            if constexpr (STRICT) {
                return st.back().first <= arr[i];
            } else {
                return st.back().first < arr[i];
            }
        };
        while (sz(st) && cmp()) {
            st.pop_back();
        }

        if (sz(st)) {
            ans[i] = st.back().second;
        } else {
            ans[i] = -1;
        }
        st.emplace_back(arr[i], i);
    }

    return ans;
}

/**
 * Computes ans[i], the closest index j to the left of i where arr[j] > arr[i]
 *
 * ans[i] = -1 if no such j exists
 */
template <typename T>
vector<int> comp_prev_gt(const vector<T>& arr) {
    return comp_prev_helper<T, true>(arr);
}

/**
 * Computes ans[i], the closest index j to the left of i where arr[j] >= arr[i]
 *
 * ans[i] = -1 if no such j exists
 */
template <typename T>
vector<int> comp_prev_ge(const vector<T>& arr) {
    return comp_prev_helper<T, false>(arr);
}

/**
 * reverses an array of indices
 *
 * specifically, it reverses the array and computes arr[i] = n - 1 - arr[i]
 */
vector<int> reverse_indices(vector<int> arr) {
    int n = sz(arr);

    reverse(begin(arr), end(arr));
    for (auto& a : arr) {
        a = n - 1 - a;
    }

    return arr;
}

/**
 * Computes ans[i], the closest index j to the right of i where arr[j] > arr[i]
 *
 * ans[i] = n if no such j exists
 */
template <typename T>
vector<int> comp_next_gt(vector<T> arr) {
    reverse(begin(arr), end(arr));

    return reverse_indices(comp_prev_gt(arr));
}

/**
 * Computes ans[i], the closest index j to the right of i where arr[j] >= arr[i]
 *
 * ans[i] = n if no such j exists
 */
template <typename T>
vector<int> comp_next_ge(vector<T> arr) {
    reverse(begin(arr), end(arr));

    return reverse_indices(comp_prev_ge(arr));
}

template <typename Cb>
struct CmpByKey {
    Cb cb;

    explicit CmpByKey(const Cb& cb) : cb(cb) {}

    template <typename T>
    bool operator()(const T& a, const T& b) const {
        return cb(a) < cb(b);
    }
};

/**
 * outputs will be in the range [0, m), returns m
 */
int coord_comp(const vector<int*>& arr) {
    vector<int> vals;
    for (auto& a : arr) {
        vals.push_back(*a);
    }

    sort(begin(vals), end(vals));
    vals.erase(unique(begin(vals), end(vals)), end(vals));

    for (auto& a : arr) {
        *a = int(lower_bound(begin(vals), end(vals), *a) - begin(vals));
    }

    return sz(vals);
}

/**
 * outputs will be in the range [0, m), returns {m, result}
 */
template <typename T>
pair<int, vector<int>> coord_comp(const vector<T>& arr) {
    vector<T> vals = arr;
    sort(begin(vals), end(vals));
    vals.erase(unique(begin(vals), end(vals)), end(vals));

    vector<int> ans;
    for (auto& a : arr) {
        ans.push_back(
            int(lower_bound(begin(vals), end(vals), a) - begin(vals)));
    }

    return {sz(vals), ans};
}

template <typename T>
bool on(T mask, int bit) {
    return (mask >> bit) & 1;
}


#line 5 "b.cpp"

using i128 = __int128_t;

string to_string(i128 x) {
    string ans;

    while (x) {
        ans.push_back(char('0' + x % 10));
        x /= 10;
    }

    reverse(begin(ans), end(ans));
    return ans;
}

ostream& operator<<(ostream& out, i128 x) {
    return out << to_string(x);
}

string gen_champ(i128 l, i128 r) {
    string ans;

    for (i128 i = l; i <= r; i++) {
        ans += to_string(i);
    }

    return ans;
}

auto data_pref = gen_champ(1, 2000);

struct P {
    i128 pow10[30];

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

// len of gen_champ(1, x - 1)
i128 get_index(i128 x) {
    i128 ans = 0;

    for (int i = 0;; i++) {
        i128 ql = P.pow10[i], qr = P.pow10[i + 1];
        if (ql <= x && x < qr) {
            ans += (i + 1) * (x - ql);
            return ans;
        } else {
            ans += (i + 1) * (qr - ql);
        }
    }
}

struct I {
    int l, r;

    I& operator&=(const I& o) {
        l = max(l, o.l);
        r = min(r, o.r);
        return *this;
    }

    friend I operator&(I a, const I& b) {
        return a &= b;
    }

    bool empty() const {
        return l > r;
    }
};

constexpr int MOD = 998244353;

bool matches(char ca, char cb) {
    return ca == cb || ca == '?' || cb == '?';
}

bool matches(const string& a, const string& b) {
    int n = sz(a);

    for (int i = 0; i < n; i++) {
        if (!matches(a[i], b[i])) {
            return false;
        }
    }

    return true;
}

int search(const string& a, const string& b) {
    int n = sz(a), m = sz(b);

    for (int i = 0; i + m <= n; i++) {
        if (matches(a.substr(i, m), b)) {
            return i;
        }
    }

    return -1;
}

template <typename Cb>
void go_rev(const string& s, int m_len, int ind, const Cb& cb) {
    auto gc = [&](int i) -> char {
        if (0 <= i && i < sz(s)) {
            return s[i];
        }
        return '?';
    };

    for (int i = 0; i < 10; i++) {
        ind -= m_len;
        for (int j = 0; j < m_len; j++) {
            if (gc(ind + j) != '?') {
                int cx = gc(ind + j) - '0';
                if (j == m_len - 1) {
                    cb(j, cx + i);
                } else {
                    cb(j, cx);
                }
            }
        }
    }
}

template <typename Cb>
void go_fwd(const string& s, int m_len, int ind, const Cb& cb) {
    auto gc = [&](int i) -> char {
        if (0 <= i && i < sz(s)) {
            return s[i];
        }
        return '?';
    };

    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < m_len; j++) {
            if (gc(ind + j) != '?') {
                int cx = gc(ind + j) - '0';
                if (j == m_len - 1) {
                    cb(j, cx - i);
                } else {
                    cb(j, cx);
                }
            }
        }
        ind += m_len;
    }
}

void solve() {
    string s;
    cin >> s;

    int n = sz(s);

    {
        int cans = search(data_pref, s);
        if (cans != -1) {
            cout << cans + 1 << endl;
            return;
        }
    }

    i128 ans = 1e36;
    // all 9 case
    for (int m = 3; m <= n; m++) {
        i128 ql = P.pow10[m] - 10, qr = P.pow10[m] + 10;
        auto c_string = gen_champ(ql, qr);

        int cans = search(c_string, s);
        if (cans != -1) {
            ans = min(ans, get_index(ql) + cans);
            ;
        }
    }

    // no carry
    for (int m = 3; m <= n; m++) {
        for (int cs = -m * 10 - 2; cs <= 0; cs++) {
            if (cs + 10 * m < n) {
                continue;
            }
            vector<I> digits(m, {0, 9});
            digits[0] &= {1, 9};
            for (int i = 0; i < 10; i++) {
                if (cs + i * m < n) {
                    digits[m - 1] &= {0, 9 - i};
                }
            }

            go_fwd(s, m, cs, [&](int digit, int x) -> void {
                digits[digit] &= {x, x};
            });

            bool bad = false;

            for (auto& a : digits) {
                bad |= a.empty();
            }

            if (bad) {
                continue;
            }

            i128 cv = 0;
            for (auto& a : digits) {
                cv = cv * 10 + a.l;
            }
            if (get_index(cv) - cs == 1386) {
                dbg(m, cs);
            }
            ans = min(ans, get_index(cv) - cs);
        }
    }

    // carry
    for (int m = 3; m <= n; m++) {
        for (int i9 = 1; i9 < m; i9++) {
            for (int mid = -m - 2; mid <= n + m + 2; mid++) {
                vector<I> digits(m, {0, 9});
                digits[0] &= {1, 9};
                digits[m - i9 - 1] &= {0, 8};
                fill(begin(digits) + m - i9, end(digits), I {9, 9});

                bool bad = false;

                go_rev(s, m, mid, [&](int digit, int x) -> void {
                    digits[digit] &= {x, x};
                });
                go_fwd(s, m, mid, [&](int digit, int x) -> void {
                    if (digit >= m - i9) {
                        if (x) {
                            bad = true;
                        }
                        return;
                    } else if (digit == m - i9 - 1) {
                        x--;
                    }
                    digits[digit] &= {x, x};
                });

                for (auto& a : digits) {
                    bad |= a.empty();
                }

                if (bad) {
                    continue;
                }

                i128 cv = 0;
                for (auto& a : digits) {
                    cv = cv * 10 + a.l;
                }
                ans = min(ans, get_index(cv + 1) - mid);
            }
        }
    }

    cout << int((ans + 1) % MOD) << endl;
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    int tcs;
    cin >> tcs;
    while (tcs--) {
        solve();
    }
}