#include <bits/stdc++.h>
#define lll __int128
using namespace std;
lll pw[31],pre[31];string str;int n;
void write(lll x){if(x<10)putchar(x+'0');else write(x/10),putchar(x%10+'0');}
int bits(lll x){int c=0;while(x)++c,x/=10;return c;}
string to_s(lll x)
{
	string s;
	while(x)
	{
		s+=x%10+'0';
		x/=10;
	}
	reverse(s.begin(),s.end());return s;
}
lll ID(lll x)
{
	int lg=bits(x);lll ans=pre[lg-1];
	ans+=(x-pw[lg-1]+1)*lg;
	return ans;
}
lll ans=1e36,cans=1e36;
int match(string s,string t)
{
	for(int i=0;i+t.size()-1<s.size();++i)
	{
		bool ok=1;
		for(int j=0;j<t.size();++j)if(t[j]!='?'&&s[i+j]!=t[j]){ok=0;break;}
		if(ok)return i;
	}
	return -1;
}
set<lll> st;
void check(lll x)
{//printf("check(");write(x);printf(")\n");
	if(st.find(x)!=st.end())return;
	st.insert(x);
	int lg=bits(x);
	if(x>cans)return;
	string s;
	lll y=x;
	while(s.size()<n-1+lg)s+=to_s(y++);
//	printf("s:%s\n",s.c_str());
	int tt=match(s,str);
	if(~tt)
	{
//		printf("success\n");
		ans=ID(x-1)+1+tt;
		cans=x;
	}
}
struct Limit{int a,b,c;Limit(){}Limit(int _a,int _b,int _c){a=_a;b=_b;c=_c;}};
int w[31][31],ww[31];
void solve(vector<Limit> vl,int k)
{
	int mxa=0;
	for(auto L:vl)mxa=max(mxa,L.a);
	for(int i=0;i<=mxa;++i)for(int j=1;j<=k;++j)w[i][j]=-1;
	for(auto L:vl)
	{
		if(~w[L.a][L.b]&&w[L.a][L.b]!=L.c)return;
		w[L.a][L.b]=L.c;
	}
	for(int i=k;i>=1;--i)
	{
		for(int j=1;j<=k;++j)ww[j]=-1;bool ok=1;
		for(int j=0;j<=mxa;++j)
		{
			for(int _=1;_<i;++_)if(~w[j][_])
			{
				if(~ww[_]&&ww[_]!=w[j][_]){ok=0;break;}
				ww[_]=w[j][_];
			}
			if(!ok)break;
		}
		if(ok)
		{
			for(int j=1;j<i;++j)if(!~ww[j])ww[j]=j==1;
			lll W=0;
			for(int j=1;j<i;++j)W=W*10+ww[j];
			W*=pw[k-i+1];
			for(int _=0;_<=8;++_)for(int __=1;__<=mxa;++__)check(W+(_+1)*pw[k-i]-__);
		}
	}
}
void dosolve(int k)
{
	for(int j=0;j<k;++j)
	{
		vector<Limit> Lim;
		for(int i=0;i<n;++i)if(str[i]!='?')
		{
			Lim.push_back(Limit((j+i)/k,(j+i)%k+1,str[i]-'0'));
		}
		solve(Lim,k);
	}
}
int TT;
int main()
{
	pw[0]=1;for(int i=1;i<=36;++i)pw[i]=10*pw[i-1];
	pre[0]=0;for(int i=1;i<=30;++i)pre[i]=pre[i-1]+i*(pw[i]-pw[i-1]);
//	printf("pre:");for(int i=1;i<=30;++i)write(pre[i]),putchar(32);putchar(10);
	scanf("%d",&TT);while(TT--)
	{
		cin>>str;n=str.size();
		ans=1e36,cans=1e36;
		st.clear();
		for(int i=1;i<=999;++i)check(i);
		for(int i=4;i<=25;++i)for(int j=1;j<=25;++j)check(pw[i]-j);
		for(int i=4;i<=25;++i)dosolve(i);
//		printf("ans:");write(ans);putchar(10);
		printf("%d\n",(int)(ans%998244353));
		printf("cans:");write(cans);putchar(10);
	}
}