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

const int N = 1e6 + 50;
const int MOD = 998244353;

int fail[N], cnt[N], k;
char s[N];
vector<int> g[N];
int path[N], hh, tt, ans[N];

void get_fail (char *s, int n) {
    fail[0] = fail[1] = 0;
    for (int i = 1; i < n; i ++) {
        int j = fail[i];
        while (j && s[j] != s[i]) j = fail[j];
        fail[i + 1] = (s[j] == s[i]) ? j + 1 : 0;
    }
    // for (int i = 1; i <= n; i ++) 
    //     printf("%d ", fail[i]);
}

void dfs (int u, int p) {
    int pre = hh;
    while (hh <= tt && path[hh] * 2 <= u) {
        cnt[path[hh] * 2 % k] --;
        hh ++;
    }
    ans[u] = cnt[u % k] + (u % k == 0);
    if (u) path[++ tt] = u, cnt[u * 2 % k] ++;
    // cout << ans[u] << ' ' << u << endl;
    for (int v : g[u]) {
        if (v == p) continue;
        dfs (v, u);
    }
    if (u) tt --, cnt[u * 2 % k] --;
    while (pre <= hh) hh --, cnt[path[hh] * 2 % k] ++;
}

int main() {
#ifdef LOCAL
    clock_t c1 = clock();
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    // ===================================================    
    int T; scanf ("%d", &T);
    while (T --) {
        scanf ("%s%d", s, &k);
        int n = strlen (s);
        for (int i = 0; i < k; i ++) cnt[i] = 0;
        for (int i = 0; i <= n; i ++) g[i].clear (), ans[i] = 0;
        hh = 1, tt = 0;
        get_fail (s, n);
        for (int i = 1; i <= n; i ++) {
            g[fail[i]].push_back (i);
            g[i].push_back (fail[i]);
        }
        dfs (0, 0);
        int res = 1;
        for (int i = 1; i <= n; i ++) 
            res = (ll)res * (ans[i] + 1) % MOD;
        printf("%d\n", res);
    }
    // ===================================================    
#ifdef LOCAL
    cerr << "Time Used: " << clock() - c1 << "ms" << endl;
#endif
    return 0;
}