#include <bits/stdc++.h>

using namespace std;
#define int long long
#define endl '\n'
#define eb emplace_back
#define INF (int)(1e18)
#define pii pair<int, int> 
#define dbg(x...) do{cout<<#x<<" -> ";err(x);}while (0)
void err(){cout<<'\n';cout.flush();}
template<class T, class... Ts>
void err(T arg, Ts... args) {
    cout<<arg<< ' ';
    err(args...);
}

const int MOD = 998244353;
void run() {
    string str;
    cin >> str;
    int n = str.size();
    str = "_" + str;
    int K;
    cin >> K;
    vector<int> z(n + 1, 0);
    vector<vector<int> > sum(K, vector<int>(n / K + 5, 0));
    for (int i = 2, l = 0, r = 0; i <= n; i++) {
        z[i] = i > r ? 1 : min(z[1 + i - l], r - i + 1);
        if (!z[i]) z[i]++;
        while (i + z[i] - 1 <= n && str[i + z[i] - 1] == str[z[i]]) z[i]++;
        z[i]--;
        if (i + z[i] - 1 > r) {
            l = i, r = i + z[i] - 1;
        }
    }
    for (int i = 2; i <= n; i++) {
        if (z[i] - i + 1 >= K) {
            // dbg(i, z[i]);
            int len = z[i] - i + 1;
            int l = 2 * i + K - 2, r = 2 * i + len / K * K - 2;
            sum[2 * i % K][l / K]++;
            sum[2 * i % K][r / K + 1]--;
        }
    }
    int ans = 1;
    vector<int> arr(n + 1, 0);
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < sum[i].size(); j++) {
            if (j) sum[i][j] = (sum[i][j] + sum[i][j - 1]) % MOD;
            if (j * K + i <= n) arr[j * K + i] = sum[i][j];
        }
    }
    for (int i = K; i <= n; i += K) arr[i] = (arr[i] + 1) % MOD;
    // for (int i = 1; i <= n; i++) dbg(i, arr[i]);
    for (int i = 1; i <= n; i++) ans = ans * (arr[i] + 1) % MOD;
    cout << ans << endl;
  




    return;
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        run();
    }


    return 0;
}