#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];
int ans[N], Next[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];
	}
}

void dfs(int u)
{
	node[2 * u % k].push_back(2 * u);
	int pos = upper_bound(node[u % k].begin(), node[u % k].end(), u) - node[u % k].begin();
	ans[u] = node[u % k].size() - pos;
	for(int v: g[u]) dfs(v);
	node[2 * u % k].pop_back();
}

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 = ans[i] + 1;
			res = res * cur % mod;
		}
		printf("%lld\n", res);
	}

	return 0; 
}