#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
const int N = 1050;
const int Mod = 998244353;
int f[N][N],g[N];
char dr[N];
int xu[N];
bool val[N];
struct Info
{
    int len,tot;
}lump[N];
int has[N];
int n,m;
int getint()
{
    int res=0;
    char ch=getchar();
    while((ch<'0' || ch>'9') && ch!='-')
        ch=getchar();
    bool fan=0;
    if(ch=='-')
    {
        fan=1;
        ch=getchar();
    }
    while('0'<=ch && ch<='9')
    {
        res=res*10+ch-'0';
        ch=getchar();
    }
    if(fan)
        res=-res;
    return res;
}
void Add(int &x,int y)
{
    x+=y;
    if(x>=Mod)
        x-=Mod;
}
int cheng(int x,int y)
{
    long long z=x;
    z*=y;
    z%=Mod;
    x=z;
    return x;
}
void Init()
{
    int i,j;
    f[0][0]=1;
    for(i=1;i<N;i++)
    {
        for(j=0;j<N;j++)
            f[i][j]=f[i-1][j];
        for(j=1;j<N;j++)
            Add(f[i][j],f[i-1][j-1]);
    }
    g[0]=0;
    for(i=1;i<N;i++)
    {
        g[i]=g[i-1];
        Add(g[i],g[i-1]);
        int sum=0;
        for(j=0;j<N;j++)
        {
            Add(g[i],cheng(sum,f[i-1][j]));
            if(j>=1)
                Add(sum,f[i-1][j-1]);
        }
    }
}
bool Chu()
{
    int i;
    for(i=xu[0];i>=1;i--)
    {
        if(xu[i]&1)
        {
            if(i>1)
                xu[i-1]+=10;
        }
        xu[i]/=2;
    }
    while(xu[0]>0 && xu[xu[0]]==0)
        xu[0]--;
}
void task()
{
    int i,j;
    scanf("%s",dr+1);
    n=strlen(dr+1);
    for(i=1;i<=n;i++)
        xu[n-i+1]=dr[i]-'0';
    xu[1]++;
    for(i=1;i<=n;i++)
    {
        if(xu[i]>9)
        {
            xu[i]=0;
            xu[i+1]++;
        }
        else
            break;
    }
    if(i>n)
    {
        n++;
        xu[n]=1;
    }
    xu[0]=n;
    n=-1;
    while(xu[0])
    {
        n++;
        val[n]=xu[1]%2;
        Chu();
    }
    int tot=0;
    m=0;
    for(i=n;i>=0;i--)
    {
        if(val[i])
        {
            m++;
            lump[m].len=i;
            lump[m].tot=tot;
            tot++;
        }
    }
    int ans=0;
    for(i=1;i<=m;i++)
        Add(ans,g[lump[i].len]);
    memset(has,0,sizeof has);
    for(i=m;i>=1;i--)
    {
        int sum=has[0];
        for(j=1;j<N;j++)
        {
            if(j>=lump[i].tot)
                Add(ans,cheng(sum,f[lump[i].len][j-lump[i].tot]));
            Add(sum,has[j]);
        }
        for(j=0;j<N;j++)
        {
            if(j>=lump[i].tot)
                Add(has[j],f[lump[i].len][j-lump[i].tot]);
        }
    }
    printf("%d\n",ans);
}
int main()
{
    Init();
    int T=getint();
    while(T--)
        task();
    return 0;
}