#include <string>
#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;

const __int128_t INF = __int128_t(3) << 123;

string to_string_i128(__int128_t x) {
	string res;
	do {
		res += int(x % 10) + '0';
		x /= 10;
	} while (x > 0);
	reverse(res.begin(), res.end());
	return res;
}

__int128_t get_minimum(int d, const vector<string>& s) {
	// step #1. no special border
	int n = s.size();
	assert(n <= 10);
	__int128_t ans = INF;
	for (int i = 0; i < 10; i++) {
		bool f = true;
		vector<int> bit(d, 0);
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < d; k++) {
				if (s[j][k] != '?') {
					if (k == d - 1) {
						f = f && (int(s[j][k] - '0') == i + j);
					} else {
						bit[k] |= 1 << int(s[j][k] - '0');
					}
					if (k == 0 && s[j][k] == '0') {
						f = false;
					}
				}
			}
		}
		for (int j = 0; j < d - 1; j++) {
			if (bit[j] & (bit[j] - 1)) {
				f = false;
			}
		}
		if (f) {
			__int128_t mul = 10, subans = i;
			for (int j = d - 2; j >= 0; j--) {
				int dig = (j != 0 ? 0 : 1);
				if (bit[j] != 0) {
					dig = __builtin_ctz(bit[j]);
				}
				subans += mul * dig;
				mul *= 10;
			}
			ans = min(ans, subans);
		}
	}

	// step #2. has special border
	for (int i = 0; i < 10; i++) {
		if (i + n < 10) {
			continue;
		}
		for (int j = 0; j < 9; j++) {
			for (int k = (j != 0 ? 1 : 2); k < d; k++) {
				bool f = true;
				vector<int> bit(d, 0);
				for (int x = 0; x < n; x++) {
					for (int y = 0; y < d; y++) {
						if (s[x][y] != '?') {
							if (y == d - 1) {
								f = f && (int(s[x][y] - '0') == (i + x) % 10);
							} else if (y >= k) {
								f = f && (int(s[x][y] - '0') == (i + x < 10 ? 9 : 0));
							} else if (y == k - 1) {
								f = f && (int(s[x][y] - '0') == (i + x < 10 ? j : j + 1));
							} else {
								bit[y] |= 1 << int(s[x][y] - '0');
							}
							if (y == 0 && s[x][y] == '0') {
								f = false;
							}
						}
					}
				}
				for (int x = 0; x < d - 1; x++) {
					if (bit[x] & (bit[x] - 1)) {
						f = false;
					}
				}
				if (f) {
					__int128_t mul = 10, subans = i;
					for (int x = d - 2; x >= k; x--) {
						subans += mul * 9;
						mul *= 10;
					}
					subans += mul * j;
					mul *= 10;
					for (int x = k - 2; x >= 0; x--) {
						int dig = (x != 0 ? 0 : 1);
						if (bit[x] != 0) {
							dig = __builtin_ctz(bit[x]);
						}
						subans += mul * dig;
						mul *= 10;
					}
					ans = min(ans, subans);
				}
			}
		}
	}

	return ans;
}

__int128_t get_index(__int128_t g) {
	__int128_t mul = 1;
	__int128_t ans = 0;
	int digits = 1;
	while (mul * 10 < g) {
		ans += mul * 9 * digits;
		mul *= 10;
		digits += 1;
	}
	ans += (g - mul) * digits;
	return ans;
}

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

__int128_t solve(const string& S) {
	// step #1. check 2-digits or less
	int L = S.size();
	string str;
	for (int i = 1; i <= 99; i++) {
		str += to_string(i);
	}
	int basepos = wildcard_find(str, S);
	if (basepos != -1) {
		return basepos;
	}

	// step #2. calculation: non-border case
	__int128_t ans = INF;
	for (int d = 3; d <= L + 1; d++) {
		for (int i = 0; i < d; i++) {
			vector<string> slist;
			for (int j = -i; j < L; j += d) {
				string subs(d, '?');
				for (int k = 0; k < d; k++) {
					if (0 <= j + k && j + k < L) {
						subs[k] = S[j + k];
					}
				}
				slist.push_back(subs);
			}
			__int128_t res = get_minimum(d, slist);
			if (res != INF) {
				__int128_t subans = get_index(res) + i;
				ans = min(ans, subans);
			}
		}
	}

	// step #3. calculation: border case
	__int128_t mul = 100;
	for (int d = 3; d <= L + 1; d++) {
		string str;
		for (__int128_t i = mul - L; i <= mul + L; i++) {
			str += to_string_i128(i);
		}
		int subpos = wildcard_find(str, S);
		if (subpos != -1) {
			__int128_t subans = get_index(mul - L) + subpos;
			ans = min(ans, subans);
		}
		mul *= 10;
	}

	return ans;
}

int main() {
	int T;
	cin >> T;
	for (int id = 1; id <= T; id++) {
		string S;
		cin >> S;
		__int128_t ans = solve(S);
		cout << int((ans + 1) % 998244353) << endl;
	}
	return 0;
}