#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], n;

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

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)
{
	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", str);
		scanf("%d", &k);
		n = strlen(str);
		_for(i, 0, n) g[i].clear();
		GetNxt();
		
		dfs(0);

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

	return 0; 
}