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

const int N = 1000100, M = 998244353;
char s[N];
int n, k, nxt[N];

int exgcd(int a, int b, int &x, int &y) {
    if (!b) { x = 1, y = 0; return a; }
    int g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

void solve() {
    cin >> s + 1 >> k;
    n = strlen(s + 1);
    nxt[0] = -1;

    long long ans = 1;
    for (int i = 1; i <= n; i++) {
        int p = nxt[i - 1];
        while (~p && s[p + 1] != s[i]) p = nxt[p];
        nxt[i] = p + 1;

        int t = 2 * (i - nxt[i]), x, y;
        int g = exgcd(t, k, x, y);
        if (i % g != 0) continue;
        x = 1ll * x * (i / g) % k;
        y = 1ll * y * (i / g) % t;

        auto q = 1ll * k / g * t;

        int num = (i - x + q - 1) / q;
        ans = ans * (1 + num) % M;
    }
    cout << ans << "\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(0), cout.tie(0);
    int T;
    for (cin >> T; T; T--) solve();
}