#include "bits/stdc++.h"
using namespace std;
#define int int64_t
#define i128 __int128_t
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

const int mod = 998244353;

string s;

std::string to_string(__int128 num) {
    if (num == 0) return "0";

    bool is_negative = num < 0;
    std::string result;

    if (is_negative) num = -num;

    while (num > 0) {
        result += '0' + (num % 10);  // Append last digit
        num /= 10;                   // Remove last digit
    }

    if (is_negative) result += '-';  // Add negative sign if needed

    std::reverse(result.begin(), result.end());  // Reverse to correct order
    return result;
}

namespace util {
	string qmk[500];
	void init() {
		qmk[0] = "";
		for (int i=1; i<500; i++) {
			qmk[i] = qmk[i-1]+"?";
		}
	}
	int len(i128 s) {
		return sz(to_string(s));
	}
	i128 ksm(int a, int b) {
		i128 res=1;
		for (int i=0; i<b; i++) {
			res = res*a;
		}
		return res;
	}
	i128 answer(i128 v) {
		if (v==0) return 0;
		v--;
		if (v==0) return 0;
		i128 f = len(v);
		i128 pv = ksm(10,f-1);
		return f*(v-pv+1)+answer(pv);
	}
	__int128 sto128(const std::string& str) {

	    __int128 result = 0;
	    bool is_negative = (str[0] == '-');
	    size_t start = is_negative ? 1 : 0;
	
	    for (size_t i = start; i < str.size(); ++i) {
	        if (str[i] < '0' || str[i] > '9') {
	            throw std::invalid_argument("Invalid character in string.");
	        }
	        result = result * 10 + (str[i] - '0');
	    }
	    return is_negative ? -result : result;
	}
}

namespace brutal_check {
	const int LIM = 9999;
	bool equal(string s1, string s2) {
		if (sz(s1) != sz(s2)) return 0;
		for (int i=0; i<sz(s1); i++) {
			if (s1[i]!=s2[i] && s1[i]!='?' && s2[i]!='?') return 0;
		}
		return 1;
	}
	bool check(i128 start,string s) {
		string s1 = "";
		for (i128 i=start; sz(s1) < sz(s); i++) {
			s1 = s1+to_string(i);
		}
		s1.resize(sz(s));
		return equal(s,s1);	
	}
	i128 cp10() {
		i128 res = -1;
		for (int len = 1; len <= 25; len++) {
			i128 v = util::ksm(10,len);
			i128 xx = util::answer(v);
			for (int expa = 0; expa < 60; expa++) {
				string ss = util::qmk[expa]+s;
				for (int cv = v; cv >= max((i128)1,v-60); cv--) {
					if (check(cv,ss)) {
						i128 ans = util::answer(cv) + expa + 1;
						if (res==-1) res = ans;
						res = min(res,ans);
					}
				}
			}
		}
		return res;
	}
	
	i128 go() {
		i128 res = -2;
		for (int i=1; i<=LIM; i++) {
			int l = util::len(i);
			for (int pad=0; pad<l; pad++) {
				string ss = util::qmk[pad]+s;
				if (check(i,ss)) {
					i128 ans = util::answer(i)+pad;
					if (res==-2) res = ans;
					else res = min(res,ans);
				}
			}
		}
		return res+1;
	}
}

namespace large_check {
	const int LIM = 25;
	
	/*
	casework on:
	- length of numbers [assume stays constant for this one]
	- greatest index that changes in value
		- from ...x99999 to ...x+100000
	*/
	
	int cor[26];
	
	bool compatible(string s, string s1) {
		assert(sz(s)==sz(s1));
		memset(cor,-1,sizeof(cor));
		for (int i=0; i<sz(s); i++) {
			if ('a' <= s1[i] && s1[i] <= 'z' && s[i] != '?') {
				int k = s1[i] - 'a';
				int v = s[i] - '0';
				if (cor[k]==-1) cor[k] = v;
				if (cor[k] != v) return 0;
			}
			if ('0' <= s1[i] && s1[i] <= '9') {
				int v = s1[i] - '0';
				if (s[i]=='?') continue;
				int v1 = s[i]-'0';
				if (v != v1) return 0;
			}
		}
		return 1;
	}
	i128 check_no_change(int len, string s, int pad=0) {
		//pad s with additional ?s
		int need = (len-sz(s)%len)%len;
		s.resize(sz(s)+need,'?');
		//fill in everything BUT units [they don't change]
		char cur = 'a';
		string s1; s1.resize(sz(s),'?');
		for (int r=0; r+1<len; r++) {
			for (int i=0; i*len<sz(s); i++) {
				s1[i*len+r] = cur;
			}
			cur++;
		}
		if (!compatible(s,s1)) return -1;
		if (cor[s1[0]-'a'] == 0) return -1;
		for (int i=0; i<26; i++) {
			if (cor[i]==-1) cor[i] = 0;
		}
		if (cor[s1[0]-'a'] == 0) cor[s1[0]-'a']=1;
		for (int i=0; i<sz(s1); i++) {
			if (i%len == len-1) continue;
			s1[i] = '0'+cor[s1[i]-'a'];
		}
		for (int s0 = 0; s0<10; s0++) {
			int cv = s0;
			string s2 = s1;
			for (int i=0; i*len<sz(s); i++) {
				if (cv==10) return -1;
				s2[i*len+len-1] = cv+'0';
				cv++;
			}
			if (compatible(s,s2)) {
				string first = s2.substr(0,len);
				i128 ans = util::sto128(first);
				i128 res = util::answer(ans)+pad+1;
				return res;
			}
		}
		return -1;
		
	}
	i128 check(int len, int ind, string s, int pad=0) {
		//pad s with additional ?s
		int need = (len-sz(s)%len)%len;
		s.resize(sz(s)+need,'?');
		string s1; s1.resize(sz(s),'?');
		i128 lok = len-ind%len; //length of known
		i128 vok = util::ksm(10,lok)-1; //value of known
		i128 iok = ind/len; //index [in lengths] of known
				
		for (int i=0; i*len<sz(s); i++) {
			string v = to_string(vok-(iok-i));
			v = v.substr(sz(v)-lok,sz(v));
			s1.replace(i*len + ind%len, lok, v);
		}
		//r=ind%len+1
		
		int rr = ind%len-1;
		for (int i=0; i*len<sz(s); i++) {
			int pos = i*len+rr;
			if (pos < ind) s1[pos] = 'a';
			else s1[pos] = 'b';
		}
		
		char cur = 'c';
		for (int r=ind%len-2; r>=0; r--) {
			for (int i=0; i*len<sz(s); i++) {
				int pos = i*len+r;
				s1[pos] = cur;
			}
			cur++;
		}
	
		if (!compatible(s,s1)) return -1;
		if (cor[0]==9 || cor[1]==0) return -1;
		
		if (cor[0]==-1 && cor[1]==-1) {
			cor[0] = 0, cor[1] = 1;
		} else if (cor[0]==-1) {
			cor[0] = cor[1]-1;
		} else if (cor[1]==-1) {
			cor[1] = cor[0]+1;
		} else if (cor[0]+1!=cor[1]) {
			return -1;
		}
		if (cor[s1[0]-'a']==0) return -1;

		for (int i=2; i<26; i++) {
			if (cor[i]==-1) cor[i] = 0;
		}
		if (cor[s1[0]-'a']==0) cor[s1[0]-'a']=1;
		
		string first = s1.substr(0,len);
		for (int i=0; i<len; i++) {
			if ('a' <= first[i] && first[i] <= 'z') {
				first[i] = '0' + cor[first[i]-'a'];
			}
		}
		
		i128 ans = util::sto128(first);
		i128 res = util::answer(ans)+pad+1;
		return res;
	}
	
	i128 go() {
		i128 res = -1;
		for (int len=2; len<=LIM; len++) {
			for (int pad=0; pad<len; pad++) {
				string ss = util::qmk[pad]+s;
				int rem = (len-sz(ss)%len)%len;
				ss.resize(sz(ss)+rem,'?');
				for (int ind=0; ind<sz(ss); ind++) {
					if (ind%len==0) continue;
					i128 v = check(len,ind,ss,pad);
					if (v==-1) continue;
					if (res==-1) {
						res = v;
					}
					res = min(res,v);
				}
			}
		}
		for (int len=2; len<=LIM; len++) {
			for (int pad=0; pad<len; pad++) {
				string ss = util::qmk[pad]+s;
				i128 v = check_no_change(len,ss,pad);
				if (v==-1) continue;
				if (res==-1) res = v;
				res = min(res,v);
			}
		}
		return res;
	}
}

i128 minn(i128 a, i128 b) {
	if (a==-1) return b;
	if (b==-1) return a;
	return min(a,b);
}

void solve() {
	cin>>s;
	i128 c = minn(brutal_check::cp10(),minn(brutal_check::go(),large_check::go()));
	c %= mod;
	cout<<to_string(c)<<"\n";
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	util::init();
		
	int t; cin>>t;
	while (t--) {
		solve();
	}
	return 0;
}