#include <iostream>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <set>
#include <cstring>
#include <array>
#pragma GCC optimize(2)
//#include <bits/stdc++.h>
#define rep(i,from,to) for(int i=from;i<to;i++)
#define ite2(x,y,arr) for(auto [x,y]:arr)
#define pdd pair<double, double>
#define ite(i,arr) for(auto &i:arr)
#define MID(l,r) int mid=(l+r)>>1
#define ALL(arr) arr.begin(),arr.end()
#define AXY(a,x,y) int x=a.first,y=a.second
#define vc vector
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;


#define FTY


namespace G {
#ifdef FTY
    const double eps = 1e-8;
    const double PI = acos(-1);
    struct Point {
        double x, y;
        Point() {
            x = 0, y = 0;
        }
        Point(double x, double y) {
            this->x = x;
            this->y = y;
        }
    };
    bool operator<(Point a, Point b) {
        return a.x < b.x || a.x == b.x && a.y < b.y;
    }
    Point operator +(Point a, Point b) {
        return Point(a.x + b.x, a.y + b.y);
    }
    Point operator -(Point a, Point b) {
        return Point(a.x - b.x, a.y - b.y);
    }
    Point operator *(double a, Point b) {
        return Point(a * b.x, a * b.y);
    }
    Point operator *(Point b, double a) {
        return Point(a * b.x, a * b.y);
    }
    Point operator /(Point b, double a) {
        return Point(b.x / a, b.y / a);
    }
    double len(Point a) {
        return sqrt(a.x * a.x + a.y * a.y);
    }
    double dis(Point a, Point b) {
        return len(a - b);
    }
    bool operator ==(Point a, Point b) {
        return dis(a, b) <= eps ;
    }
    bool operator !=(Point a, Point b) {
        return !(a == b);
    }
    double operator *(Point a, Point b) {
        return a.x * b.x + a.y * b.y;
    }

    double operator ^(Point a, Point b) {
        return a.x * b.y - a.y * b.x;
    }

    double getAngel(double b, double a, double c) {
        return acos((a * a + c * c - b * b) / (2 * a * c));
    }
    double getAngel(Point a, Point b) {
        return acos(a * b / len(a) / len(b));
    }
    Point inter(Point p, Point v, Point q, Point w) {

        Point u = p - q;
        double t = (w ^ u) / (v ^ w);
        return p + t * v;
    }


#endif
}
using namespace G;
#define int ll
const int mod = 998244353;
//template <class T>
//T __gcd(T a, T b) {
//    if (a < b) swap(a, b);
//    return b ? __gcd(b, a % b) : a;
//}
template <class T>
T __lcm(T a, T b) {
    T num = __gcd(a, b);
    return a / num * b;
}
inline int lowbit(int num) { return num & (-num); }
inline int qmi(int a, int b) {
    a %= mod;
    ll res = 1;
    while (b) {
        if (b & 1) res = (ll)res * a % mod;
        a = (ll)a * a % mod;
        b >>= 1;
    }
    return res;
}
int inv(int num) {
    return qmi(num, mod - 2);
}

const int N = (int)1e6+10;
int h[N];
int base[N];
string s;
const int p = 12289;
void builtHash() {
    h[0] = 0;
    int n = s.size();
    rep(i, 1, n+1) {
        h[i] = (h[i - 1] * p + s[i - 1]) % mod;
    }

    base[0] = 1;
    rep(i, 1, n+1) {
        base[i] = base[i - 1] * p%mod;
    }
}

int getHash(int l, int r) {
    return (h[r + 1] - h[l] * base[r + 1 - l] % mod + mod) % mod;
}

void solve() {
    cin >> s;

    builtHash();
    int n;
    n = s.size();
    int k;
    cin >> k;
    vi pre(n * 2 + k,0);
    rep(i, 0, n) {
        int l = i, r = n - 1;
        while (l <= r) {
            int mid = l + r >> 1;
            int len = mid - i + 1;
            if (getHash(0, len - 1) == getHash(i, mid)) {
                l = mid + 1;
            }
            else r = mid - 1;
        }
        int len = r - i + 1;
        if (len-i>= k) {
            int tmp = (len-i) - (len-i) % k;
            l = (i+ k)*2-k-1;
            r = (i+tmp)*2-tmp-1;
            pre[l + 1]++;
            pre[r + 1+k]--;
        }
    }

    rep(i, 1, n + 1) {
        pre[i] += i - k >= 0 ? pre[i - k] : 0;
    }
    ll res = 1;
    rep(i, 1, n + 1) {
        pre[i]++;
        res = res * pre[i] % mod;
    }
    cout << res << endl;

}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tc = 1;
    cin >> tc;
    for (int i = 1; i <= tc; i++) {
        solve();
    }
}

/*
1
abababac
2


*/