#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
#define ll long long
#define fastio ios::sync_with_stdio(0), cin.tie(0)

using namespace std;
const int mod = 998244353;

// 一個字串的後綴可以和字串本身匹配到多長從第i項開始一路到n-1
inline vector<int> z_function(string s)
{
    int n = s.size();
    vector<int> z(n, 0);
    for(int i = 1, l = 0, r = 0; i < n; i++) {
        if(i <= r && z[i - l] < r - i + 1) {
            z[i] = z[i - l];
        }
        else {
            z[i] = max(0, r - i + 1);
            while(i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        }
        if(i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
    z[0] = n;
    return z;
}

void solve()
{
    // cin >> n;
    string s;
    cin >> s;
    int n = s.size();
    int k;
    cin >> k;
    vector<int> z = z_function(s);
    vector<int> cnt(n, 0);
    vector<int> v(n + 1, 0);
    for(int i = 0; i < n; i++) {
        if(z[i] - i < 0) continue;
        int lens = z[i] - i; // len of choose substring
        int step_to_next = lens / k;
        int start = i * 2 + k - 1;
        int stop = start + step_to_next * k;
        if(start < n) v[start]++;
        if(stop < n) v[stop]--;
    }
    vector<int> ans(n, 0);
    for(int i = 0; i < k; i++) {
        int now = 0;
        for(int j = i; j < n; j += k) {
            now += v[j];
            ans[j] = now;
        }
    }
    int final_ans = 1;
    for(int i = 0; i < n; i++) {
        final_ans = (final_ans * (ans[i] + 1)) % mod;
    }
    cout << final_ans << '\n';
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:4:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::__cxx11::basic_string<char>::_Alloc_hider::~_Alloc_hider()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = char]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/string:54:
/usr/include/c++/13/bits/basic_string.h:181:14: note: called from here
  181 |       struct _Alloc_hider : allocator_type // TODO check __is_final
      |              ^~~~~~~~~~~~