#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define data dataa
#define rank rk
using LL=long long;
using ULL=unsigned long long;
using LD=long double;
const int MOD=998244353;
char s[30];
int S[500010],cnt,a[30],need[30],n;
__int128 pw[30];
__int128 cal(__int128 x)
{
    int n=0;
    for(__int128 y=x;y;y/=10,n++);
    __int128 res=(x-pw[n-1]+1)*n;
    for(int i=n-1;i;i--)res+=(pw[i]-pw[i-1])*i;
    return res;
}
int main()
{
    pw[0]=1;
    rep(i,26)pw[i]=pw[i-1]*10;
    rep(i,int(1e5)+10)
    {
        int tmp[10],tc=0;
        for(int x=i;x;x/=10)tmp[++tc]=x%10;
        reverse(tmp+1,tmp+tc+1);
        rep(j,tc)S[++cnt]=tmp[j];
    }
    int T;
    for(scanf("%d",&T);T--;)
    {
        scanf("%s",s+1);
        n=strlen(s+1);
        rep(i,n)a[i]=s[i]=='?'?-1:s[i]-'0';
        int pos=-1;
        for(int i=1;i+n-1<=cnt;i++)
        {
            bool flag=1;
            rep(j,n)if(a[j]!=-1&&a[j]!=S[i+j-1]){flag=0;break;}
            if(flag){pos=i;break;}
        }
        if(pos!=-1){printf("%d\n",pos);continue;}
        __int128 ans=0;
        rep(i,n)if(a[i]!=-1)ans=ans*10+a[i];else if(ans)ans*=10;else ans=1;
        if(a[1]==0)
        {
            ans=1;
            rep(i,n)if(a[i]!=-1)ans=ans*10+a[i];else ans*=10;
            ans=cal(ans-1)+2;
        }
        else ans=cal(ans-1)+1;
        for(int len=6;len<=n;len++)
        rep(off,min(n-1,len))
        rep(nine,len-1)
        {
            rep(carry,10)
            {
                bool ok=1;
                rep(i,len)need[i]=-1;
                rep(i,nine)need[i+1]=9;
                need[1]=10-carry;
                rep(i,n)
                if(a[i]!=-1)
                {
                    int seg=i<=off?0:(i-off-1)/len+1,rk=i<=off?off-i:len-1-(i-off-1)%len;
                    if(nine==len-1&&i>off+(carry-1)*len)
                    {
                        seg=carry+(i-off-(carry-1)*len-1)/(len+1);
                        rk=len-(i-off-(carry-1)*len-1)%(len+1);
                    }
                    int d=a[i];
                    if(rk==0)d=(d-seg+10)%10;
                    else if(rk<=nine)
                    {
                        if(seg<carry){if(d!=9){ok=0;break;}}
                        else
                        {
                            if(d!=0){ok=0;break;}
                            else d=9;
                        }
                    }
                    else if(rk==nine+1)
                    {
                        if(seg<carry){if(d==9){ok=0;break;}}
                        else d=(d-1+10)%10;
                    }
                    if(rk==len){if(d!=0){ok=0;break;}}
                    else if(need[rk+1]==-1)need[rk+1]=d;
                    else if(need[rk+1]!=d){ok=0;break;}
                }
                if(!ok||need[len]==0)continue;
                __int128 tans=0;
                for(int i=len;i;i--)if(need[i]!=-1)tans=tans*10+need[i];else if(tans)tans*=10;else tans=1;
                tans=cal(tans-1)+(len-off+1);
                ans=min(ans,tans);
            }
        }
        printf("%d\n",int(ans%MOD));
    }
    return 0;
}