#include <bits/stdc++.h>
#define N 1000005
using i64 = long long;
using namespace std;

string s;
int n, k, nxt[N], ans[N], kmod[N];
vector<int> adj[N], trash;
deque<int> node;
void dfs(int cur, int fa)
{
    while (!node.empty() && node.front() * 2 <= cur)
    {
        trash.push_back(node.front());
        kmod[2 * node.front() % k]--;
        node.pop_front();
    }
    ans[cur] = kmod[cur % k];
    if (cur % k == 0)
        ans[cur]++;
    node.push_back(cur);
    kmod[2 * cur % k]++;
    for (const int &i : adj[cur])
        dfs(i, cur);
    while (!trash.empty() && trash.back() * 2 > fa)
    {
        node.push_front(trash.back());
        kmod[trash.back() * 2 % k]++;
        trash.pop_back();
    }
    kmod[2 * cur % k]--;
    node.pop_back();
}
void solve()
{
    cin >> s >> k;
    n = s.length();
    s = ' ' + s;
    for (int i = 2, h = 0; i <= n; i++)
    {
        while (h && s[h + 1] != s[i])
            h = nxt[h];
        if (s[h + 1] == s[i])
            h++;
        nxt[i] = h;
        adj[h].push_back(i);
    }
    adj[0].push_back(1);
    dfs(0, -1);
    int sum = 1;
    for (int i = 1; i <= n; i++)
        sum = (i64)sum * (ans[i] + 1) % 998244353;
    for (int i = 0; i < n; i++)
        adj[i].clear();
    node.clear();
    trash.clear();
    fill(kmod, kmod + k, 0);
    cout << sum << '\n';
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
}