#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
#define int long long
const int N = 1e6+10;
const int mod = 998244353;
int qmi(int a,int b) {
    int res = 1;
    for (; b; b >>= 1, a = a * a % mod) {
        if (b & 1)res = res * a % mod;
    }
    return res;
}
vector<int>e[N];
int cnt[N];
int k,ans;
void dfs(int u,int fa){
    int x = cnt[u % k] + 1;
    if (u % k == 0 and u != 0)x++;
    ans = ans * x % mod;

    if (u != 0)cnt[u * 2 % k]++;
    for (auto v: e[u]) {
        if (v == fa)continue;
        dfs(v, u);
    }
    if (u != 0)cnt[u * 2 % k]--;
}
void solve(int tc) {
    string s;
    cin >> s >> k;
    s = " " + s;
    int n = s.size();
    for (int i = 0; i < n; i++)e[i].clear(), cnt[i] = 0;
    vector<int> nxt(n);
    e[0].push_back(1);
    for (int i = 2; i < n; i++) {
        nxt[i] = nxt[i - 1];
        while (nxt[i] and s[i] != s[nxt[i] + 1])nxt[i] = nxt[nxt[i]];
        if (s[i] == s[nxt[i] + 1])nxt[i]++;
        while (2 * nxt[i] >= i)nxt[i] = nxt[nxt[i]];
        e[nxt[i]].push_back(i);
    }
    ans = 1;
    dfs(0, -1);
    cout << ans;
}
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc = 1;
    cin >> tc;
    for (int i = 1; i <= tc; i++) {
        solve(i);
    }
}