#include<iostream>
#include<cstring>
#define ll long long
using namespace std;

const int MAXN = 1e6 + 10;
const int MOD = 998244353;
char str[MAXN];
int z[MAXN], len;

void GetZ(char str[], int n, int z[]) {
    int l = 0, r = 0;
    z[0] = n;
    for (int i = 1; i < n; i++) {
        z[i] = i > r ? 0 : min(r - i + 1, z[i - l]);
        while (z[i] + i < n && str[z[i]] == str[i + z[i]]) z[i]++;
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
}
int T;
int k;
int a[MAXN];
int main() {
#ifdef TanJI
    freopen("D:\\Cpp\\1.in", "r", stdin);
    freopen("D:\\Cpp\\1.out", "w", stdout);
#endif
    scanf("%d", &T);
    while (T--) {
        scanf("%s", str);
        scanf("%d", &k);
        len = strlen(str);
        GetZ(str, len, z);
        for (int i = 0; i < len; i++) a[i] = 0;
        for (int i = 0; i < len; i++) {
            //z[i]是长度，z[i] - 1是下标，
            if (z[i] > i) {
                int l = (z[i] - i) / k - 1, r = -1;
                int offset = i + z[i] - 1 - ((z[i] - i) % k);
                a[offset - l * k]++;
                a[offset - r * k]--;
            }
        }
        for (int i = k; i < len; i++) {
            a[i] += a[i - k];
        }
        ll ans = 1;
        for (int i = 0; i < len; i++) 
            ans = ans * (a[i] + 1) % MOD;
        printf("%lld\n", ans);
    }
    return 0;
}