ABBA Counting

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

const int MOD = 998244353;
const int ROOT = 3;

int modPow(ll a, ll e) {
    ll r = 1;
    while (e > 0) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return (int)r;
}

void ntt(vector<int>& a, bool invert) {
    int n = (int)a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        int wlen = modPow(ROOT, (MOD - 1) / len);
        if (invert) wlen = modPow(wlen, MOD - 2);

        for (int i = 0; i < n; i += len) {
            ll w = 1;
            int half = len >> 1;
            for (int j = 0; j < half; j++) {
                int u = a[i + j];
                int v = (int)(a[i + j + half] * w % MOD);
                int x = u + v;
                if (x >= MOD) x -= MOD;
                int y = u - v;
                if (y < 0) y += MOD;
                a[i + j] = x;
                a[i + j + half] = y;
                w = w * wlen % MOD;
            }
        }
    }

    if (invert) {
        int invN = modPow(n, MOD - 2);
        for (int& x : a) x = (int)((ll)x * invN % MOD);
    }
}

vector<int> pw2;
string T;
int halfLen;

int codeChar(char c) {
    if (c == '?') return 0;
    if (c == 'a') return 1;
    return 2;
}

void addCorrelation(const vector<int>& x, const vector<int>& y, int vx, int vy, vector<int>& dest) {
    int d = (int)x.size();
    int sz = 1;
    while (sz < 3 * d) sz <<= 1;

    vector<int> a(sz), b(sz);
    for (int i = 0; i < d; i++) a[d - 1 - i] = (x[i] == vx);
    for (int i = 0; i < 2 * d; i++) b[i] = (y[i % d] == vy);

    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < sz; i++) a[i] = (int)((ll)a[i] * b[i] % MOD);
    ntt(a, true);

    for (int s = 0; s < d; s++) dest[s] += a[d - 1 + s];
}

int calcPeriod(int d) {
    vector<int> x(d), y(d);
    for (int i = 0; i < halfLen; i++) {
        x[i % d] |= codeChar(T[i]);
        y[i % d] |= codeChar(T[halfLen + i]);
    }

    for (int i = 0; i < d; i++) {
        if (x[i] == 3 || y[i] == 3) return 0;
    }

    const int DIRECT_LIMIT = 80;
    if (d <= DIRECT_LIMIT) {
        int res = 0;
        for (int s = 0; s < d; s++) {
            int bad = 0, freeCnt = 0;
            for (int i = 0; i < d; i++) {
                int a = x[i], b = y[(i + s) % d];
                if ((a == 1 && b == 2) || (a == 2 && b == 1)) {
                    bad = 1;
                    break;
                }
                if (a == 0 && b == 0) freeCnt++;
            }
            if (!bad) {
                res += pw2[freeCnt];
                if (res >= MOD) res -= MOD;
            }
        }
        return res;
    }

    vector<int> bad(d), freeCnt(d);
    addCorrelation(x, y, 1, 2, bad);
    addCorrelation(x, y, 2, 1, bad);
    addCorrelation(x, y, 0, 0, freeCnt);

    int res = 0;
    for (int s = 0; s < d; s++) {
        if (bad[s] == 0) {
            res += pw2[freeCnt[s]];
            if (res >= MOD) res -= MOD;
        }
    }
    return res;
}

int main() {
    setIO();

    pw2.assign(400005, 1);
    for (int i = 1; i < (int)pw2.size(); i++) pw2[i] = (pw2[i - 1] * 2LL) % MOD;

    int tc;
    cin >> tc;
    while (tc--) {
        int n;
        cin >> n >> T;
        halfLen = n / 2;

        vector<int> divisors;
        for (int i = 1; (ll)i * i <= halfLen; i++) {
            if (halfLen % i == 0) {
                divisors.push_back(i);
                if (i * i != halfLen) divisors.push_back(halfLen / i);
            }
        }
        sort(divisors.begin(), divisors.end());

        vector<int> exact(halfLen + 1);
        for (int d : divisors) exact[d] = calcPeriod(d);

        for (int i = 0; i < (int)divisors.size(); i++) {
            int d = divisors[i];
            for (int j = i + 1; j < (int)divisors.size(); j++) {
                int e = divisors[j];
                if (e % d == 0) {
                    int sub = (int)((ll)exact[d] * (e / d) % MOD);
                    exact[e] -= sub;
                    if (exact[e] < 0) exact[e] += MOD;
                }
            }
        }

        int ans = 0;
        for (int d : divisors) {
            ans += exact[d];
            if (ans >= MOD) ans -= MOD;
        }
        cout << ans << char(10);
    }
}