#include <bits/stdc++.h>
#define all(a) begin(a), end(a)
#define int __int128_t
using namespace std;

string to_string(int x){
	if (x == 0) {
		return "0";
	} else if (x < 0) {
		return "-" + to_string(x);
	}
	string res;
	while (x) {
		res.push_back('0' + x % 10);
		x /= 10;
	}
	assert(res.size());
	reverse(res.begin(), res.end());
	return res;
}

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

int f(int x){
	--x;
	int pw = 1, b = 1;
	int res = 0;
	while (x >= pw) {
		int l = pw, r = min(x, pw * 10 - 1);
		res += b * (r - l + 1);
		pw *= 10; ++b;
	}
	return res + 1;
}



string g(int pos, int len){
	--pos;
	int pw = 1, b = 1;
	while (pos >= pw * b * 9) {
		pos -= pw * b * 9;
		pw *= 10; ++b;
	}

	string t;
	assert(pos / b + pw > 0);
	int base = pos / b + pw, rem = pos % b;
	while (t.size() < len + 50) {
		t += to_string(base); ++base;
	}
	return t.substr(rem, len);
}

int to_int(string s){
	int res = 0;
	for (auto c : s) {
		res = res * 10 + (c - '0');
	}
	return res;
}

bool matched(string s, string t){
	if (s.size() != t.size()) return false;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '?') continue;
		if (s[i] != t[i]) return false;
	}
	return true;
}

int ans;
string s; 
void test(int x){
	if (x <= 0) return;
	// cout << x << ' ' << g(x, s.size()) << endl;
	if (matched(s, g(x, s.size()))) {
		ans = min(ans, x);
	}
}

bool can(string& s, int idx, char c){
	if (s[idx] == '?') return true;
	return s[idx] == c;
}

string superimpose(string& s, int l){
	string r(l, '?');
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '?') continue;
		if (r[i % l] == '?') {
			r[i % l] = s[i];
		} else if (r[i % l] != s[i]) {
			r[i % l] = 'X';
		}
	}
	return r;
}


void solve() {
	cin >> s;
	ans = (__int128_t) 1 << 120;
	
	for (int pw10 = 1; pw10 < 1e27; pw10 *= 10) {
		for (int y = -50; y <= 50; y++) {
			test(f(pw10) + y);
		}
	}
	for (int i = 1; i <= 10000; i++) {
		test(i);
	}
	for (int l = 3; l <= 26; l++) {
		for (int pad = 0; pad < l; pad++) {
			string t = string(pad, '?') + s;
			int rem = l - t.size() % l;
			t += string(rem, '?');
			assert(t.size() % l == 0);
			assert(t.size() / l <= 10);

			int n = t.size();
			for (int i = 0; i < n / l; i++) {
				for (int c = 0; c < l; c++) {
					for (int x = 0; x <= 9; x++) {
						string u; u.push_back('0' + x);
						for (int i = 0; i < c; i++) {
							u.push_back('9');
						}
						bool ok = true;
						for (int j = l - u.size(); j < l; j++) {
							ok &= can(t, i * l + j, u[j - (l - u.size())]);
						}
						if (!ok) continue;
						string La = superimpose(t, l).substr(0, l - c - 1);
						for (auto c : La) {
							if (!c) ok = false;
						}
						if (!ok) continue;
						int y = to_int(La);
						y = y * 10 + x;
						for (int j = 0; j < c; j++) {
							y = y * 10 + 9;
						}
						// cout << y << endl;
						test(f(y) - i * l + pad);
					}
				}
			}
		}
	}
	const int MOD = 998244353;
	cout << ans % MOD << '\n';
}

int32_t main(){
#ifndef LOCAL
	cin.tie(0)->sync_with_stdio(false);
#endif
	int64_t t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
}