#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int maxn = 1000025;

vector<int> buc[maxn];

size_t fail[maxn];
vector<size_t> g[maxn];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        string s;
        int k;
        cin >> s >> k;
        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;
        }

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

        vector<int> ans(s.size() + 1);

        const auto In = [&](int i) {
            {
                auto &b = buc[i * 2 % k];
                b.push_back(i * 2);
            }
            {
                const auto &b = buc[i % k];
                // cerr << "i = " << i << ';';
                // for (int j: b)
                //     cerr << j << ',';
                // cerr << endl;
                ans[i] = b.end() - upper_bound(b.begin(), b.end(), i);
            }
        };

        const auto Out = [&](int i) {
            {
                auto &b = buc[i * 2 % k];
                b.pop_back();
            }
        };

        const auto dfs = [&]() {
            vector<int> stk;
            stk.emplace_back(0);
            while (!stk.empty()) {
                int i = stk.back(); stk.pop_back();
                if (i >= 0) {
                    In(i);
                    stk.emplace_back(~i);
                    for (size_t j: g[i]) {
                        stk.emplace_back(j);
                    }
                } else {
                    Out(~i);
                }
            }
        };

        dfs();

        // 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;
}