#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;
}
int foo(int t, int k, int v) { // tx + ky = v, x,y >= 0
    if (v < 0) return 0;
    int x, y;
    int g = exgcd(t, k, x, y);
    if (v % g != 0) return 0;
    t /= g, k /= g, v /= g;
    x = 1ll * x * v % k;
    if (x < 0) x += k;
    assert(1ll * t * x % k == v % k);
    long long a = v - 1ll * x * t, b = 1ll * k * t;
    if (a < 0) return 0;
    return a / b + 1;
}

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;
        ans = ans * (1 + foo(2 * (i - nxt[i]), k, i - k)) % M;
    }
    cout << ans << "\n";
}

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