#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

typedef long long ll;
const int mod = 998244353;
const int N = 1e6 + 10;
vector<int> g[N], q[N];
int up[N][25], ans1[N], ans2[N], cnt[N], n;

void AddEdge(int u, int v) {
	g[u].push_back(v);
	up[v][0] = u;
}

char str[N];
int k;
int nxt[N];
void GetNxt() {
	int i = 0, j = -1, len = strlen(str);
	nxt[0] = -1;
	while (i < len) {
		if (j == -1 || str[i] == str[j]) {nxt[++i] = ++j; AddEdge(j, i);}
		else j = nxt[j];
	}
}

void dfs(int u)
{
	int v = u;
	for(int j = 20; j >= 0; j--)
		if(2 * up[v][j] - u > 0)
			v = up[v][j];
	v = up[v][0];
	q[v].push_back(u);

	for(int v: g[u]) dfs(v);
}

void dfs2(int u)
{
	cnt[2 * u % k]++;
	ans1[u] = cnt[u % k];
	for(auto x: q[u])
		ans2[x] = cnt[x % k];
	for(int v: g[u]) dfs2(v);
	cnt[2 * u % k]--;
}

int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		scanf("%s", str);
		scanf("%d", &k);
		n = strlen(str);
		_for(i, 1, n) g[i].clear(), q[i].clear(), cnt[i] = 0;
		GetNxt();

		//_for(i, 1, n) printf("%d %d\n", i, nxt[i]);

		_for(i, 1, n)
			_for(j, 1, 20)
				up[i][j] = up[up[i][j - 1]][j - 1];
		
		dfs(0);
		dfs2(0);

		ll ans = 1;
		_for(i, 1, n)
		{
			ll cur = ans1[i] - ans2[i] + 1;
			ans = ans * cur % mod;
		}
		printf("%lld\n", ans);

		//_for(i, 1, n) printf("!! %d %d\n", i, ans1[i]);
	}

	return 0; 
} 

/*
2
abababac
2
abababac
2


*/