#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

typedef __int128 dll;

const int MOD = 998244353;

dll len_sum[30];
void calc_len_sum() {
	len_sum[1] = 9;
	for (int i = 2; i < 30; i++) {
		len_sum[i] = len_sum[i - 1] * 10;
	}
	for (int i = 1; i < 30; i++) {
		len_sum[i] = len_sum[i] * i;
	}
}

dll func(string S) {
	int n = S.size();

	dll ret = 0;
	for (int i = 1; i < n; i++) {
		ret += len_sum[i];
	}

	assert(S[0] != '0');
	S[0] -= 1;

	dll num = 0;
	for (int i = 0; i < S.size(); i++) {
		num = 10 * num + (S[i] - '0');
	}

	return ret + num * n + 1;
}
void func_test() {
	cout << (ll)func("1") << '\n';
	cout << (ll)func("10") << '\n';
	cout << (ll)func("99") << '\n';
	cout << (ll)func("100") << '\n';
}

string to_string(dll n) {
	if (n == 0) {
		return "0";
	}

	string S;
	while (n) {
		S += (char)('0' + (n % 10));
		n /= 10;
	}
	reverse(S.begin(), S.end());

	return S;
}
dll to_int(string S) {
	dll ret = 0;
	for (int i = 0; i < S.size(); i++) {
		ret = 10 * ret + (S[i] - '0');
	}
	return ret;
}

string incr(string S) {
	return to_string(to_int(S) + 1);
}
string decr(string S) {
	return to_string(to_int(S) - 1);
}

bool test(string S, string T) {
	if (S.size() != T.size()) {
		return false;
	}

	for (int i = 0; i < S.size(); i++) {
		if (S[i] != '?' && S[i] != T[i]) {
			return false;
		}
	}
	return true;
}

string fill_zero(int n, string S) {
	int m = n - (int)S.size();
	return string(m, '0') + S;
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	
	calc_len_sum();
	// func_test();

	string SM;
	for (int i = 1; i <= 150; i++) {
		SM += to_string(i);
	}

	int T;
	cin >> T;
	while (T--) {
		string S;
		cin >> S;

		bool found = false;
		for (int i = 0; i <= SM.size() - S.size(); i++) {
			if (test(S, SM.substr(i, S.size()))) {
				found = true;
				cout << i + 1 << '\n';
				break;
			}
		}
		if (found) {
			continue;
		}

		dll ans = 1e38;
		for (int d = 3; d <= (int)S.size() + 1; d++) {
			// case 1. {d, d, ..., d+1, ..., d+1}

			for (int f = 0; f < d; f++) for (int b = 0; b <= d; b++) {
				string N = string(f, '?') + S + string(b, '?');
				int sz = N.size();
				// fix the position of 999...9

				for (int i = 0; i + d < sz; i += d) {
					// N[i .. i+d-1] is 99..9

					if ((sz - d - i) % (d + 1) != 0) {
						continue;
					}

					int small_cnt = i / d + 1;
					int large_cnt = (sz - d - i) / (d + 1);

					string B(d, '9');
					dll bn = to_int(B);

					if (bn - small_cnt + 1 <= bn / 10) {
						continue;
					}

					string X;
					for (dll x = bn - small_cnt + 1; x <= bn + large_cnt; x++) {
						X += to_string(x);
					}

					if (test(N, X)) {
						ans = min(ans, func(to_string(bn - small_cnt + 1)) + f);
					}
				}
			}

			// case 2. {d, d, d, ... d}

			for (int f = 0; f < d; f++) for (int b = 0; b < d; b++) {
				if ((f + b + S.size()) % d != 0) {
					continue;
				}
				string N = string(f, '?') + S + string(b, '?');

				int sz = N.size();
				assert(sz % d == 0);

				vector<string> V(sz / d);
				for (int i = 0; i < sz; i += d) {
					V[i / d] = N.substr(i, d);
				}
				int k = sz / d;

				// for (int i = 0; i < k; i++) {
				// 	cout << V[i] << endl;
				// }

				// case 2-1. there exists ...99

				for (int i = 0; i < k; i++) for (int p = 2; p < d; p++) {
					// check for first d - p - 1 digits
					string H; bool flag = true;
					
					// bool debug = false;
					// if (f == 0 && b == 3 && d == 7) {
					// 	debug = true;
					// }

					for (int pos = 0; pos < d - p - 1; pos++) {
						int num = -1;

						for (int j = 0; j < k; j++) {
							if (V[j][pos] == '?') continue;

							int x = V[j][pos] - '0';
							if (num == -1) {
								num = x;
							}
							else if (num != x) {
								flag = false;
							}
						}
						if (pos == 0 && num == 0) flag = false;
						if (!flag) break;
						if (num == -1) num = (pos == 0) ? 1 : 0;

						H += (char)('0' + num);
					}
					// if (debug) cout << i << ' ' << p << ' ' << flag << ' ' << H << endl;
					if (!flag) continue;

					// check for the (d - p - 1)-th digit
					int prv = -1, nxt = -1;
					for (int j = 0; j <= i; j++) {
						if (V[j][d - p - 1] == '?') continue;

						int x = V[j][d - p - 1] - '0';
						if (prv == -1) {
							prv = x;
						}
						else if (prv != x) {
							flag = false;
						}
					}
					for (int j = i + 1; j < k; j++) {
						if (V[j][d - p - 1] == '?') continue;

						int x = V[j][d - p - 1] - '0';
						if (nxt == -1) {
							nxt = x;
						}
						else if (nxt != x) {
							flag = false;
						}
					}
					if (!flag) continue;
					if (prv == -1 && nxt == -1) {
						if (p == d - 1) prv = 1, nxt = 2;
						else prv = 0, nxt = 1;
					}
					else if (prv == -1) {
						prv = nxt - 1;
					}
					else if (nxt == -1) {
						nxt = prv + 1;
					}
					if (prv != nxt - 1) continue;
					if (p == d - 1 && prv == 0) continue;
					if (prv < 0 || nxt > 9) continue;


					// check for the remaining p digit
					dll bn = to_int(string(p, '9'));
					dll mod = bn + 1;

					for (int j = 0; j < k; j++) {
						string X = fill_zero(p, to_string((bn + j - i) % mod));
						if (!test(V[j].substr(d - p, p), X)) {
							flag = false;
							break;
						}
					}
					if (!flag) continue;



					H += (char)('0' + prv);
					H += to_string(bn - i);


					ans = min(ans, func(H) + f);
				}

				// case 2-2. there does not exist ...99
				for (int a = 0; a + k < 100; a++) {
					bool flag = true;
					for (int j = 0; j < k; j++) {
						if (!test(V[j].substr(d - 2, 2), fill_zero(2, to_string(a + j)))) {
							flag = false;
							break;
						}
					}
					string H;
					for (int pos = 0; pos < d - 2; pos++) {
						int num = -1;

						for (int j = 0; j < k; j++) {
							if (V[j][pos] == '?') continue;

							int x = V[j][pos] - '0';
							if (num == -1) {
								num = x;
							}
							else if (num != x) {
								flag = false;
							}
						}
						if (pos == 0 && num == 0) flag = false;
						if (!flag) break;
						if (num == -1) num = (pos == 0) ? 1 : 0;

						H += (char)('0' + num);
					}
					if (!flag) continue;

					H += fill_zero(2, to_string(a));
					// if (b == 0 && f == 0 && d == 5) {
					// 	cout << H << endl;
					// }

					ans = min(ans, func(H) + f);
				}
			}
		}
		ans %= MOD;
		cout << (ll)ans << '\n';
	}
}