#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], node[N], q[N];
int ans[N], Next[N], Next2[N], cnt[N], ans1[N], ans2[N], n, k;
char str[N];

void get_next() 
{
	Next[0] = -1;
	int i = 0, j = -1;
	while(i < n)
	{
		if(j == -1 || str[i] == str[j])
		{
			i++; j++;
			Next[i] = j;
			g[Next[i]].push_back(i);
		}
		else j = Next[j];
	}

	Next2[0] = -1;
	i = 0, j = -1;
	while(i < n)
	{
		if((j == -1 || str[i] == str[j]) && 2 * j + 2 <= i + 1)
		{
			i++; j++;
			Next2[i] = j;
			q[Next2[i]].push_back(i);
		}
		else j = Next2[j];
	}
}

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

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

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

	return 0; 
}