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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

vi Z(string S) {
	vi z(sz(S));
	int l = -1, r = -1;
	rep(i,1,sz(S)) {
		z[i] = i >= r ? 0 : min(r - i, z[i - l]);
		while (i + z[i] < sz(S) && S[i + z[i]] == S[z[i]])
			z[i]++;
		if (i + z[i] > r)
			l = i, r = i + z[i];
	}
	return z;
}

const int M = 998244353;

void solve() {
	string s; cin >> s;
	vector<int> z = Z(s); z[0] = s.size();
	int n = s.size(), k; cin >> k;

	vector<int> upd(n);
	for (int i = 0; i < n; i++) {
		if (z[i] < i) continue;
		int comm = z[i] - i;

		// start from i*2 + k
		// goes for comm/k steps
		int step = comm/k;

		int start = i*2 + k - 1;
		int stop = start + step*k;

		if (start < n) upd[start]++;
		if (stop < n) upd[stop]--;
	}

	vector<int> ans(n);
	for (int i = 0; i < k; i++) {
		int cur = 0;
		for (int j = i; j < n; j += k) {
			cur += upd[j];
			ans[j] = cur;
		}
	}

	int res = 1;
	for (int i: ans) {
		res = (1LL*res*(i+1)) % M;
		//cout << i << ' ';
	}
	//cout << '\n';
	cout << res << '\n';
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0); 
	
	int t; cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}