// Author:  HolyK
// Created: Sat Sep  3 15:52:10 2022
#include <bits/stdc++.h>

template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;

constexpr int P(998244353);
inline void inc(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
inline void dec(int &x, int y) {
  x -= y;
  if (x < 0) x += P;
}
inline int mod(LL x) { return x % P; }
int fpow(int x, int k = P - 2) {
  int r = 1;
  for (; k; k >>= 1, x = 1LL * x * x % P) {
    if (k & 1) r = 1LL * r * x % P;
  }
  return r;
}
struct Z {
  int x;
  Z() : x(0) {}
  Z(int v) : x(v < 0 ? v + P : v >= P ? v - P : v) {}
  Z(LL v) : x((v %= P) < 0 ? v + P : v) {}
  explicit operator bool() { return !!x; }
  Z inv() const { return Z(fpow(x)); }
  Z pow(int k) const { return Z(fpow(x, k)); }
  Z operator-() const { return Z(P - x); }
  Z &operator+=(const Z &r) { return inc(x, r.x), *this; }
  Z &operator-=(const Z &r) { return dec(x, r.x), *this; }
  Z &operator*=(const Z &r) { return x = LL(x) * r.x % P, *this; }
  Z &operator/=(const Z &r) { return x = LL(x) * fpow(r.x) % P, *this; }
  inline friend Z operator+(const Z &a, const Z &b) { return Z(a) += b; }
  inline friend Z operator-(const Z &a, const Z &b) { return Z(a) -= b; }
  inline friend Z operator*(const Z &a, const Z &b) { return Z(a) *= b; }
  inline friend Z operator/(const Z &a, const Z &b) { return Z(a) /= b; }
  inline friend std::ostream &operator<<(std::ostream &os, const Z &r) {
    return os << r.x;
  }
};

constexpr int N(1e6 + 5);
int n, k, g[N], d[N], f[N], cnt[N];
char s[N];

std::vector<int> h[N];
void dfs(int x) {
  h[x * 2 % k].push_back(2 * x);
  int v = x % k;
  cnt[x] = h[v].end() - std::lower_bound(h[v].begin(), h[v].end(), x + 1);
  for (int i = d[x]; i < d[x + 1]; i++) {
    dfs(g[i]);
  }
  h[x * 2 % k].pop_back();
}
void solve() {
  std::cin >> s + 1 >> k;
  n = strlen(s + 1);
  for (int i = 0; i <= n + 1; i++) d[i] = 0;
  for (int i = 2, j; i <= n; i++) {
    for (j = f[i - 1]; j && s[j + 1] != s[i]; j = f[j]) ;
    f[i] = j + (s[j + 1] == s[i]);
  }
  for (int i = 1; i <= n; i++) {
    d[f[i]]++;
  }
  for (int i = 1; i <= n + 1; i++) {
    d[i] += d[i - 1];
  }
  for (int i = 1; i <= n; i++) {
    g[--d[f[i]]] = i;
  }

  dfs(0);

  int prod = 1;
  for (int i = 1; i <= n; i++) {
    // std::cerr << cnt[i] << " \n"[i == n];
    prod = (cnt[i] + 1LL) * prod % P;
  }
  std::cout << prod << "\n";
}

int main() {
  // freopen("t.in", "r", stdin);
  
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int t = 1;
  
  std::cin >> t;
  
  while (t--) {
    solve();
  }
  return 0;
}