#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int maxn = 1000025;

struct Fenwick {
    int sum[maxn];
    void add(int p, int v) {
        for (++p; p < maxn; p += p & -p)
            sum[p] += v;
    }
    int qry(int p) {
        int r = 0;
        for (++p; p > 0; p -= p & -p)
            r += sum[p];
        return r;
    }
} BIT;

vector<tuple<int,int,int>> evt[maxn];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        string s;
        int k;
        cin >> s >> k;
        vector<size_t> fail(s.size());
        for (size_t i = 1, j = 0; i < s.size(); i++) {
            while (j && s[i] != s[j]) j = fail[j - 1];
            if (s[i] == s[j]) ++j;
            fail[i] = j;
        }

        vector<vector<size_t>> g(s.size() + 1);
        for (size_t i = 0; i < s.size(); i++) {
            g[fail[i]].emplace_back(i + 1);
        }

        vector<int> df_in(s.size() + 1);
        vector<int> df_ou(s.size() + 1);
        int df_cnt = 0;
        const auto dfs = [&]() {
            vector<int> stk;
            stk.emplace_back(0);
            while (!stk.empty()) {
                int i = stk.back(); stk.pop_back();
                if (i >= 0) {
                    df_in[i] = df_cnt++;
                    stk.emplace_back(~i);
                    for (size_t j: g[i]) {
                        stk.emplace_back(j);
                    }
                } else {
                    df_ou[~i] = df_cnt;
                }
            }
        };

        dfs();


        for (int i = 0; i < k; i++)
            evt[i].clear();
        for (int i = 1; i <= s.size(); i++) {
            evt[2 * i % k].emplace_back(i, 1, i);
            evt[2 * i % k].emplace_back(i * 2, -1, i);
            evt[i % k].emplace_back(i, 2, i);
        }

        vector<int> ans(s.size() + 1);
        for (int r = 0; r < k; r++) {
            sort(evt[r].begin(), evt[r].end());
            for (auto [_, type, i]: evt[r]) {
                if (type == 2) {
                    ans[i] += BIT.qry(df_in[i]);
                } else {
                    int val = type;
                    BIT.add(df_in[i], val);
                    BIT.add(df_ou[i], -val);
                }
            }
        }

        // for (size_t i = 1; i <= s.size(); i++)
        //     cerr << ans[i] << ' ';
        // cerr << endl;
        int64_t res = 1;
        for (size_t i = 1; i <= s.size(); i++)
            res = res * (ans[i] + 1) % mod;
        cout << res << '\n';
    }
    return 0;
}