#include "iostream"
#include "cstring"
#include "cstdio"
#include "algorithm"
#include "queue"
#include "vector"
#include "queue"
#include "stack"
#include "ctime"
#include "set"
#include "map"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
typedef long long ll;
const int MAXN = 2e6 + 10;
const int P = 998244353;
int n , k;
char ch[MAXN];

int z[MAXN];
void init( char* s ) {
	int l = 0;
	rep( i , 1 , n - 1 ) {
		if( l + z[l] > i ) z[i] = min( z[i - l] , l + z[l] - i );
		while( i + z[i] < n && s[z[i]] == s[z[i] + i] ) ++ z[i];
		if( i + z[i] > l + z[l] ) l = i;
	}
	per( i , n , 1 ) z[i] = z[i - 1];
	z[1] = n;
}
int S[MAXN];
void solve() {
	scanf("%s",ch + 1);
	n = strlen( ch + 1 );
	scanf("%d",&k);
	init( ch + 1 );
//	rep( i , 1 , n ) printf("%d ",z[i]); puts("");
	rep( i , 1 , n ) if( z[i] ) {
		int se = z[i] - i + 1;
		if( se < k ) continue;
		int l = 2 * i - 1 + k - 1;
//		cout << l << ' ' << l + k * ( se / k ) << endl;
		++ S[l];
		-- S[l + k * ( se / k )];
	}
	int res = 1;
	rep( i , 1 , n ) {
		if( i >= k ) S[i] = ( S[i] + S[i - k] ) % P;
//		cout << S[i] << endl;
		res = ( res * 1ll * ( S[i] + 1 ) ) % P;
	}
	cout << res << endl;
	rep( i , 1 , n ) S[i] = z[i] = 0;
}

signed main() {
//	freopen("in","r",stdin);
//	freopen("out","w",stdout);
	int T;cin >> T;while( T-- ) solve();
//	solve();
}