#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 1500
#define P 998244353
#define ll long long
int C[N][N],s[N][N],Cnt[N],a2[N],v[N],Aha[N],pre[N],n,m,t,ans;
char b[N];
inline void Add(int &x,int y)
 {x=(x+y)%P;}
void Pretreat()
 {
     for (int i=0;i<N;i++) C[i][0]=true,s[i][0]=true;
     for (int i=1;i<N;i++)
      for (int j=1;j<=i;j++)
        C[i][j]=(C[i-1][j-1]+C[i-1][j])%P,
        s[i][j]=(s[i][j-1]+C[i][j])%P;
     for (int i=0;i<N;i++)
      for (int j=2;j<=i;j++)
        Add(Cnt[i],s[i][j-2]*1LL*C[i][j]%P);
     a2[0]=1;
     for (int i=1;i<N;i++) a2[i]=(a2[i-1] << 1)%P;
    return;
 }
void Div_2()
 {
     for (int i=n;i>=1;i--) v[i-1]+=(v[i]&1)*10,v[i]/=2;
     if (n-1&&!v[n]) n--;
     return;
 }
void GetAns(int x)
 {for (int i=0;i<x;i++) Add(ans,Cnt[x-i-1]*1LL*a2[i]%P);}
int main()
 {
     cin >> t;Pretreat();
     while (t--)
      {
          scanf("%s",b);n=strlen(b);ans=0;
          memset(Aha,0,sizeof Aha);Aha[0]=true;
          for (int i=0;i<n;i++) v[n-i]=b[i]-'0';
          for (int i=0;n>1||v[1];i++,Div_2())
           if (v[1]&1)
            {
                 if (i) GetAns(i);
                 for (int j=i;~j;j--)
                   Aha[j+1]=Aha[j];Aha[0]=false;
                 for (int j=1;j<=i;j++) pre[j]=(pre[j-1]+Aha[j])%P;
                 for (int j=1;j<=i;j++)
                   Add(ans,C[i][j]*1LL*pre[j-1]%P);
                 for (int j=0;j<=i;j++)
                   Add(Aha[j],C[i][j]);
            }
          cout <<ans<<endl;
      }
     return 0;
 }