#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=2000,p=998244353;
int cas,g[N],a[N],n,b[N],f[N];
int c[N][N];
char s[N];
void div2()
{
    for (int i=n;i>=1;i--)
    {
        g[i-1]+=g[i]%2*10;
        g[i]/=2;
    }
    while (g[n]==0&&n) n--;
}
int main()
{
    scanf("%d",&cas);
    c[0][0]=1;
    for (int i=1;i<=1000;i++)
    for (int j=0;j<=1000;j++)
        c[i][j]=(j?(c[i-1][j-1]+c[i-1][j])%p:1);
        
    for (int i=1;i<=1000;i++)
    {
        int sum=0;
        f[i+1]=f[i]*2%p;
        for (int j=2;j<=1000;j++)
        {
            sum=(sum+c[i][j-2])%p;
            f[i+1]=(f[i+1]+1LL*sum*c[i][j])%p;
        }
    }
    
    
    
    while (cas--)
    {
        scanf("%s",s+1);
        n=strlen(s+1);int m=0;
        for (int i=1;i<=n;i++) g[i]=s[n+1-i]-'0';g[1]++;
        while (n)
        {
            a[m]=g[1]%2;m++;
            div2();
        }
        n=m;
        
        int ans=0,d=0;
        for (int i=n-1;i>=0;i--)
        if (a[i])
        {
            ans=(ans+f[i])%p;
            int sum=0;
            for (int j=n;j>=i+1;j--) sum=(sum+b[j+d+1])%p;
            for (int j=i;j>=0;j--)
            {
                sum=(sum+b[j+d+1])%p;
                ans=(ans+1LL*sum*c[i][j])%p;
            }
            for (int j=0;j<=i;j++) b[j+d]=(b[j+d]+c[i][j])%p;
            d++;
        }
        for (int i=0;i<=n+10;i++) b[i]=0;
        printf("%d\n",ans);
    }
    return 0;
}