#include<iostream>
#include<cstdio>
#include<vector>
#include<bitset>
#include<algorithm>
#include<cstring>
#define mod 998244353
using namespace std;
inline int read()
{
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
int nsl[1000005];
char s[1000005];
int kmp[1000005];
int fq[1000005],nson[1000005];
vector<int>v[1000005];
void dfs1(int x,int f)
{
	if(x==0)fq[x]=0;
	else
	{
		fq[x]=fq[f];
		while(2*nson[fq[x]]<=x)fq[x]=nson[fq[x]];
	}
	for(int i=0;i<v[x].size();i++)
	{
		if(v[x][i]==f)continue;
		nson[x]=v[x][i];
		dfs1(v[x][i],x);
	}
}
vector<int>gx[1000005];
int k;
int fsl[1000005];
void dfs2(int x,int f)
{
	if(x!=0)nsl[2*x%k]++;
	//printf("%lld %lld\n",x,nsl[x%k]);
	fsl[x]+=nsl[x%k];
	for(int i=0;i<gx[x].size();i++)fsl[gx[x][i]]-=nsl[gx[x][i]%k];
	for(int i=0;i<v[x].size();i++)
	{
		if(v[x][i]==f)continue;
		dfs2(v[x][i],x);
	}
	if(x!=0)nsl[2*x%k]--;
}
int main()
{
	int t,n;
	t=read();
	for(int greg=1;greg<=t;greg++)
	{
		scanf("%s",s+1);
		n=strlen(s+1);
		k=read();
		kmp[1]=0;
		int j=0;
		for(int i=2;i<=n;i++)
		{
			while(j>=1&&s[j+1]!=s[i])j=kmp[j];
			if(s[j+1]==s[i])j++;
			kmp[i]=j;
			//printf("%d %d\n",i,kmp[i]);
		}
		for(int i=0;i<=n;i++)v[i].clear(),gx[i].clear();
		for(int i=1;i<=n;i++)v[kmp[i]].push_back(i);
		dfs1(0,0);
		//for(int i=1;i<=n;i++)printf("%d %d\n",i,fq[i]);
		for(int i=1;i<=n;i++)gx[fq[i]].push_back(i); 
		dfs2(0,0);
		int ans=1;
		for(int i=1;i<=n;i++)ans=1LL*ans*(fsl[i]+1)%mod;
		printf("%lld\n",ans);
	}
}