#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<class S,class T>
ostream& operator << (ostream &out,pair<S,T> a);
template<class T>
ostream& operator << (ostream &out,vector<T> a);
template<class...T>
ostream& operator << (ostream &out,tuple<T...> a);
#ifdef DEBUG
template<class T>
void debug(T x);
template<class T,class...S>
void debug(T x,S...y);
#else
#define debug(...) void()
#endif
using LL=__int128;
ostream& operator << (ostream &out,LL a){
	if(a>9)out<<a/10;
	return out<<int(a%10);
}
using ll=long long;
using ull=unsigned long long;
string s;
vector<pair<LL,string>>test;
string trs(LL x){
	string s;
	for(;x;x/=10)s+=x%10+'0';
	reverse(all(s));
	return s;
}
const int mod=998244353,M=30;
LL pw[M],pre[M];
LL calc(LL x){
	int k=upper_bound(pw,pw+M,x)-pw;
	return pre[k-1]+(x-pw[k-1]+1)*k;
}
void init(){
	for(int i=pw[0]=1;i<M;i++)pw[i]=pw[i-1]*10;
	// debug(ary(pw,1,27));
	for(int i=1;i<M;i++)pre[i]=pre[i-1]+i*(pw[i]-pw[i-1]);
	string s;
	for(int i=1;i<=1e3+M;i++)s+=trs(i);
	test.push_back({1,s});
	for(int i=4;i<M;i++){
		string L,R;
		for(LL x=pw[i];R.size()<M;x++)R+=trs(x);
		LL x=pw[i]-1;
		for(;L.size()<M;x--)L=trs(x)+L;
		test.push_back({calc(x)+1,L+R});
	}
	// for(auto [st,x]:test)debug(st,x);
}
void get(){
	cin>>s;
	LL ans=pw[18]*pw[18];
	for(const auto &[st,t]:test){
		for(int l=0,r=s.size()-1;r<t.size();l++,r++){
			if([&](){
				for(int i=0;i<s.size();i++){
					if(s[i]!=t[l+i]&&s[i]!='?')return 0;
				}
				return 1;
			}())ans=min(ans,st+l);
		}
	}
	// debug(ans);
	for(int len=4;len<=s.size();len++){
		for(int d=1;d<=len;d++){
			vector<string>t;
			int delta=len-d+1;
			for(int r=d-1,l=d-len;l<(int)s.size();l+=len,r+=len){
				string p;
				// if(len==4)debug(l,r);
				for(int i=l;i<=r;i++){
					if(i<0||i>=(int)s.size())p+='?';
					else p+=s[i];
				}
				// if(len==4)debug(p);
				t.push_back(p);
			}
			// if(len==5)debug(d,t);
			for(int c=0;c<=9;c++){
				int k=t.size();
				if(![&](){
					for(int i=0;i<t.size();i++){
						char ch=t[i].back();
						if(ch!='?'&&ch-'0'!=(c+i)%10)return 0;
						if((c+i)%10==9)k=i;
					}
					return 1;
				}())continue;
				for(int cnt=1;cnt<len;cnt++){
					[&](){
						// if(len==7&&d==7&&c==7&&cnt==3)debug(k,"OK");
						vector<char>res(cnt,'?');
						for(int i=0;i<t.size();i++){
							// if(len==7&&d==7&&c==7&&cnt==3)debug(t[i]);
							if(i<=k){
								for(int j=0;j<cnt;j++){
									if(t[i][j]=='?')continue;
									if(res[j]=='?')res[j]=t[i][j];
									else if(res[j]!=t[i][j])return;
								}
								for(int j=cnt;j<len-1;j++){
									if(t[i][j]=='?')continue;
									if(t[i][j]!='9')return;
								}
							}else{
								for(int j=0;j<cnt-1;j++){
									if(t[i][j]=='?')continue;
									if(res[j]=='?')res[j]=t[i][j];
									else if(res[j]!=t[i][j])return;
								}
								if(t[i][cnt-1]=='0')return;
								if(t[i][cnt-1]=='?');
								else if(res[cnt-1]=='?')res[cnt-1]=t[i][cnt-1]-1;
								else if(res[cnt-1]!=t[i][cnt-1]-1)return;
								for(int j=cnt;j<len-1;j++){
									if(t[i][j]=='?')continue;
									if(t[i][j]!='0')return;
								}
							}
							// if(len==7&&d==7&&c==7&&cnt==3)debug(res);
						}
						// if(len==7&&d==7&&c==7&&cnt==3)debug("OK2");
						if(res[0]=='0')return;
						if(k<t.size()&&res[cnt-1]=='9')return;
						// if(res[cnt-1]=='9')return;
						if(res[0]=='?')res[0]='1';
						for(int i=1;i<cnt;i++){
							if(res[i]=='?')res[i]='0';
						}
						res.resize(len);
						for(int i=cnt;i<len-1;i++)res[i]='9';
						res[len-1]=c+'0';
						// if(len==7&&d==7&&c==7&&cnt==3)debug(res);
						LL val=0;
						for(char c:res)val=val*10+c-'0';
						// if(calc(val-1)+delta<9000000){
						// 	debug(t);
						// 	debug(len,d,c,cnt);
						// 	debug(val,delta);
						// }
						ans=min(ans,calc(val-1)+delta);
					}();
				}
			}
		}
	}
	// debug(ans);
	ans=min(ans,[&](){
		LL x=1;
		for(char c:s){
			x=x*10+(isdigit(c)?c-'0':0);
		}
		return calc(x-1)+2;
	}());
	// debug(ans,mod);
	cout<<int(ans%mod)<<endl;
	// debug(trs(394238)+trs(394239)+trs(394240));
}
void clr(){}
template<bool x>
using If=typename enable_if<x>::type;
template<int i,class T>
If<i==0> otp(ostream &out,T a){
	out<<get<i>(a);
}
template<int i,class T>
If<i!=0> otp(ostream &out,T a){
	otp<i-1>(out,a),out<<','<<get<i>(a);
}
template<class...T>
ostream& operator << (ostream &out,tuple<T...> a){
	return out<<'(',otp<sizeof...(T)-1>(out,a),out<<')';
}
template<class S,class T>
ostream& operator << (ostream &out,pair<S,T> a){
	return out<<'('<<a.first<<','<<a.second<<')';
}
template<class T>
ostream& operator << (ostream &out,vector<T> a){
	out<<'[';
	for(auto x:a)out<<x<<',';
	return out<<']';
}
#ifdef DEBUG
template<class T>
void debug(T x){
	cerr<<x<<endl;
}
template<class T,class...S>
void debug(T x,S...y){
	cerr<<x<<' ',debug(y...);
}
#endif
int main(){
	int T;
	scanf("%d",&T);
	for(init();T--;clr())get();
	return 0;
}