#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define endl "\n"
#define PII pair<int,int>
const ll INF=0x3f3f3f3f;//3f3f3f3f;
const int mod=998244353;
const int N=1e6+5;
vector<int>g[N];
vector<int>cnt[N];
int ne[N],ans[N],k;
void dfs(int u){
	cnt[2*u%k].push_back(2*u);
	ans[u]=cnt[u%k].end()-upper_bound(cnt[u%k].begin(),cnt[u%k].end(),u);
	for(int &v:g[u]) dfs(v);
	cnt[2*u%k].pop_back();
}
void solve(){
	string s; cin>>s;
	int n=s.size(); s=" "+s;
	for(int i=0;i<=n;i++) g[i].clear();
	cin>>k;
	for(int i=2,j=0;i<=n;i++){
		while(j&&s[j+1]!=s[i]) j=ne[j];
		if(s[j+1]==s[i]) j++;
		ne[i]=j;
		g[ne[i]].push_back(i);
	} g[0].push_back(1);
	dfs(0);
	ll res=1;
	for(int i=1;i<=n;i++) res=res*(ans[i]+1)%mod;
	cout<<res<<endl;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T=1; cin>>T;
    while(T--) solve();
}