#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<set>
#define mo 998244353
#define maxn 1010 
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define son e[i].t
#define pow POW
#define clear(x) memset(x, 0, sizeof(x))
typedef long long ll;
using namespace std;
void gn(int &x)
{
    x = 0; int f = 1; char ch = getchar();
    while (ch < '0' || ch > '9'){
        if (ch == '-') f = -1; ch = getchar();
    }while (ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0'; ch = getchar();
    }x *= f;
}
int T, n;
int cnt[maxn][maxn], sum[maxn][maxn], f[maxn];
int o[maxn], a[maxn], len, tmp;
char s[maxn];
bool divide()
{
    if (o[1] % 2) a[len] = 1, o[1] --; ++ len;
    for (int i = tmp; i >= 1; -- i){
        if (o[i] % 2 == 0)
            o[i] /= 2; 
        else{
            o[i - 1] += 10;
            o[i] = (o[i] - 1) / 2;
        }
    }
    while (tmp && ! o[tmp]) -- tmp;
    return tmp > 0;
}
int now[maxn];
void solve()
{
    clear(a);
    scanf("%s", s + 1); tmp = strlen(s + 1); len = 0;
    for (int i = 1; i <= tmp; ++ i) o[i] = s[tmp - i + 1] - '0';
    o[1] = o[1] + 1;
    while (divide());
    clear(now);
    int tot = 0, ans = 0;
    for (int i = len; i >= 0; -- i){
        if (a[i]){
            for (int j = tot + 1; j <= 1000; ++ j) 
                ans = (ans + 1ll * now[j] * sum[i][j - tot - 1] % mo) % mo;
            for (int j = tot; j <= 1000; ++ j)
                now[j] = (now[j] + cnt[i][j - tot]) % mo;
            ++ tot;
            ans = (ans + f[i]) % mo;
        }
    }
    printf("%d\n", ans);
}
int main()
{
    cnt[0][0] = 1;
    for (int i = 0; i <= 1000; ++ i) sum[0][i] = 1;
    f[1] = 0;
    for (int i = 1; i <= 1000; ++ i){
        cnt[i][0] = cnt[i - 1][0];
        for (int j = 1; j <= 1000; ++ j)
            cnt[i][j] = (cnt[i - 1][j - 1] + cnt[i - 1][j]) % mo;
        sum[i][0] = cnt[i][0];
        for (int j = 1; j <= 1000; ++ j) sum[i][j] = (sum[i][j - 1] + cnt[i][j]) % mo;
        f[i + 1] = 2ll * f[i] % mo;
        for (int j = 2; j <= 1000; ++ j) f[i + 1] = (f[i + 1] + 1ll * cnt[i][j] * sum[i][j - 2] % mo) % mo;
    }
    scanf("%d", &T);
    while (T --) solve();
}