#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int MOD = 998244353;
const int N = int(3e6) + 5;
const int M = 33;

bitset<N> fib, s;

struct event{
    int i, dx;
};

int main() {
    cin.tie(0);
    iostream::sync_with_stdio(false);

    array<int, M> len;
    fib[0] = 1;
    fib[1] = 0;
    len[0] = len[1] = 1;
    int k = 2;
    for (int n = 2; n < N; ++k){
        len[k] = len[k - 1] + len[k - 2];
        forn(j, len[k - 1]) if (n < N) fib[n++] = fib[j];
    }

    int m = 0;
    int n;
    cin >> n;
    vector<int> q;
    forn(i, n){
        string t;
        cin >> t;
        for (char c : t) s[m++] = c - '0';
        q.push_back((q.empty() ? 0 : q.back()) + t.size());
    }
    reverse(q.begin(), q.end());

    array<queue<event>, M> evs;
    int sum = 1;
    forn(i, m + 1){
        int dp = sum;
        forn(j, M) if (!evs[j].empty() && evs[j].front().i == i){
            dp = (dp - evs[j].front().dx + MOD) % MOD;
            evs[j].pop();
        }
        if (i == q.back()){
            cout << dp << "\n";
            q.pop_back();
        }
        if (i){
            sum = (sum + dp) % MOD;
        }
        if (s[i] == 0){
            evs[0].push({i + 1, dp});
            continue;
        }
        int l = 1;
        forn(j, N){
            if (i + j == m || s[i + j] != fib[j]) break;
            if (j == len[l] - 1){
                evs[l].push({i + len[l], dp});
                ++l;
            }
        }
    }
    return 0;
}