#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 k,nxt[N],cnt[N],ans,n;
string s;
deque<int>q;
void dfs(int u,int fa) {
    vector<int> tmp;
    while (not q.empty() and q.front() * 2 <= u)cnt[q.front() * 2 % k]--, tmp.push_back(q.front()), q.pop_front();

    int x = cnt[u % k] + 1;
    if (u % k == 0 and u != 0)x++;
    ans = ans * x % mod;

    cnt[u * 2 % k]++, q.push_back(u);

    for (auto &v: e[u]) {
        dfs(v,u);
    }

    while (not tmp.empty() )cnt[tmp.back() * 2 % k]++, q.push_front(tmp.back()), tmp.pop_back();
    cnt[u * 2 % k]--, q.pop_back();
}
void solve() {
    cin >> s >> k;
    s = " " + s;
    n = s.size();
    e[0].push_back(1);
    for (int i = 2, j = 0; i < n; i++) {
        while (j and s[j + 1] != s[i])j = nxt[j];
        if (s[j + 1] == s[i])j++;
        nxt[i] = j;
        e[j].push_back(i);
    }
    ans = 1;
    dfs(0, -1);
    cout << ans << "\n";
    for (int i = 0; i < n; i++)e[i].clear();
    q.clear();
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tc = 1;
    cin >> tc;
    while(tc--){
        solve();
    }
}