#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second
#define int __int128

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int mod=998244353;
int ksm(int x,ll y,int p=mod){
	int ans=1;y%=(p-1);
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}
int cmod(int x){if(x>=mod)x-=mod;return x;}

template<typename T>void cmax(T &x,T v){x=max(x,v);}
template<typename T>void cmin(T &x,T v){x=min(x,v);}

string out(int x){
	if(x<0)return "-"+out(-x);
	string res="";res+=((char)(x%10+'0'));
	if(x>=10)return out(x/10)+res;
	return res;
}
int getpos(int w){
	int ans=0;
	for(int t=0,P=1;t<=30;t++,P*=10)if(w>=P)ans+=w-P;
	return ans+1;
}
int chk_pos(string A,string B){
	for(int i=0;i+B.size()<=A.size();i++){
		bool chk=true;
		for(int j=0;j<B.size();j++)if(B[j]!='?'&&A[i+j]!=B[j]){chk=false;break;}
		if(chk)return i;
	}
	return -1;
}
const int D=26;
string get_str(int x){
	string res="";
	for(int i=x-D;i<=x+D;i++)if(i>=1)res+=out(i);
	return res;
}

ostream &operator<<(ostream &fout,__int128 num){
	fout<<out(num);
	return fout;
}

// double At=0,Bt=0;

void solve(){
	string str;cin>>str;

	// case 1
	int w=0,ans=0;
	if(str[0]=='?')w=1;
	else if(str[0]=='0')w=10,ans++;
	else w=str[0]-'0';

	for(int i=1;i<str.size();i++){
		w=w*10;
		if(str[i]!='?')w+=str[i]-'0';
	}
	ans+=getpos(w);

	// for(int i=1;i<=3000000;i++)if(getpos(i)>=8058869){cout<<"i = "<<out(i)<<endl;break;}

	// cout<<"w = "<<out(w)<<" ans = "<<out(ans)<<" "<<out(ans%mod)<<endl;

	// case 2

	auto get_val=[&](int l,int r,int B)->__int128 {
		// cout<<"get_val l,r = "<<l<<" "<<r<<" B = "<<B<<endl;
		if(l>r)return 0;
		int nl=l,nr=r;
		string now="";for(int i=l;i<=r;i++)now+=str[i];
		while(l>=0)l-=B,r-=B;
		while(l<str.size()){
			for(int i=l;i<=r;i++)if(i>=0&&i<str.size()){
				if(str[i]=='?')continue;
				if(now[i-l]=='?')now[i-l]=str[i];
				else if(now[i-l]!=str[i])return -1;
			}
			l+=B,r+=B;
		}
		if(now[0]=='0')return -1;
		if(now[0]=='?')now[0]='1';
		int w=0;
		for(int i=0;i<=r-l;i++){
			w=w*10;
			if(now[i]!='?')w+=now[i]-'0';
		}
		return w;
	};

	string tmp=str;

	auto test=[&](int w){
		string A=get_str(w);
		int P=chk_pos(A,tmp);
		// if(w==3989999){
		// 	cout<<"test w = "<<w<<" P = "<<P<<endl;
		// 	cout<<"A = "<<A<<endl;
		// }
			// cout<<getpos(469579807)<<" "<<getpos(469579807-D)<<" "<<w-D<<endl;
		if(P!=-1)cmin(ans,P+getpos(max((__int128)(1),w-D)));
	};

	// test(3989999);
	for(int i=1;i<=2000;i++)test(i);
	if(ans<=10000000){
		cout<<ans<<endl;
		return ;
	}

	// int now=ans;ans=1e30;

	// test(469579807);
	// cout<<"ans = "<<ans<<endl;
	// exit(0);

	for(int i=1;i<=25;i++)str='?'+str;

	// {
		// int l=0,r=8;
	// At-=clock();
	for(int l=0;l<str.size();l++){
		for(int r=max(l,(__int128)(25));r<str.size();r++)if(r-l+1<=25){
			// cout<<"try l,r = "<<l<<" "<<r<<endl;
			// int l=1,r=5;
			int t=max(l,r-1);
			function<void(int)>dfs=[&](int now){
				if(now==r+1){
					// cout<<"try str = "<<str<<endl;
					int w=get_val(l,t-1,r-l+1);
					if(w==-1)return ;
					for(int i=t;i<=r;i++)w=w*10+str[i]-'0';
					test(w);
					// cout<<"w = "<<w<<" -> ans = "<<ans<<endl;
					// if(w==65054)cout<<" w = "<<w<<endl;
					return ;
				}
				if(str[now]!='?')dfs(now+1);
				else{
					for(int c=0;c<=9;c++)str[now]=(char)(c+'0'),dfs(now+1),str[now]='?';
				}
			};
			dfs(t);
			// cout<<" -> ans = "<<ans<<endl;
		}
	}
	// At+=clock();

	// cout<<"now ans = "<<ans<<endl;
	// exit(0);

	// for(int i=1;i<=25;i++)str='?'+str;
	// ans-=25;

	// cout<<"str = "<<str<<endl;
	// cout<<" now ans = "<<ans<<endl;
	
	// Bt-=clock();
	for(int l=0;l<str.size();l++){
		for(int r=max(l,(__int128)(25));r<str.size();r++)if(r-l+1<=25){
			for(int t=r;t>=l+1;t--){
				if(str[t]!='9'&&str[t]!='?')break;
				int w=get_val(l,t-2,r-l+1);
				if(w==-1)continue;
				if(str[t-1]=='?'){
					w=w*10;int tmp=w;
					for(int c=0;c<=9;c++){
						w=tmp+c;
						for(int i=t;i<=r;i++)w=w*10+9;
						test(w);
					}
				}
				else{
					w=w*10+str[t-1]-'0';
					for(int i=t;i<=r;i++)w=w*10+9;
					test(w);
				}
				// test(w);
				// if(w==6999){
				// 	cout<<"test l,r = "<<l<<" "<<r<<" t = "<<t<<" w = "<<w<<endl;
				// 	cout<<" -> ans = "<<ans<<endl;
				// }
			}
		}
	}
	// Bt+=clock();

	// ans+=25;

	for(int t=1,P=9;t<=25;t++,P=P*10+9)test(P);

	// ans+=25;cmin(ans,now);

	cout<<ans%mod<<endl;
	// cout<<ans<<endl;
	// cout<<getpos(3989999)+2<<endl;
	// cout<<out(ans%mod)<<endl;

	// ans=1e30;
	// for(int w=1;w<=200000;w++)test(w);
	// cout<<ans%mod<<endl;
}

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
#endif

	// double St=clock();
	// cout<<out(getpos(9))<<" "<<out(getpos(11))<<endl;
	int tt=read();while(tt--)solve();

	// cout<<"Time = "<<clock()-St<<" At,Bt = "<<At<<" "<<Bt<<endl;

	return 0;
}