// A.cpp
// author : georgeyucjr
#include <bits/stdc++.h>

using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using arr3 = std ::array<int, 3>;
using arr4 = std ::array<int, 4>;
using pii = std ::pair<int, int>;

#define ALL(vc) std ::begin(vc), std ::end(vc)
#define rep(i, f, t, ...) for (std ::decay<decltype(f + t)>::type i = f, _END_##i = t, ##__VA_ARGS__; i <= _END_##i; ++i)
#define per(i, f, t, ...) for (std ::decay<decltype(f + t)>::type i = f, _END_##i = t, ##__VA_ARGS__; i >= _END_##i; --i)
#define eb emplace_back
#define pb push_back
#define mkp make_pair
#define FILEIO(filename) freopen(filename ".in", "r", stdin), freopen(filename ".out", "w", stdout)
template <class T, class U> inline T ceil(T &&x, U &&y) { return (x > 0 ? (x + y - 1) / y : x / y); }
template <class T, class U> inline T floor(T &&x, U &&y) { return (x > 0 ? x / y : (x - y + 1) / y); }
template <class T, class U> inline T divmod(T &&x, U &&y) { auto &&q = floor(x, y); return mkp(q, x - q * y); }
template <class T> constexpr static T inf = std ::numeric_limits<T>::max() >> 1;
template <class T> inline int SZ(T &&x) { return x.size(); }
template <typename T> inline T Abs(const T &x) { return x < 0 ? -x : x; }
template <typename T> inline T sqr(const T &x) { return x * x; }
template <typename T> inline T Max(const T &x) { return x; }
template <typename T> inline T Min(const T &x) { return x; }
template <typename T, typename U, typename... Args> inline T Max(const T &x, const U &y, const Args &...args) { return x < y ? Max(y, args...) : Max(x, args...); }
template <typename T, typename U, typename... Args> inline T Min(const T &x, const U &y, const Args &...args) { return x < y ? Min(x, args...) : Min(y, args...); }
template <typename T, typename... Args> inline void chkmax(T &d, const Args &...x) { d = Max(d, x...); }
template <typename T, typename... Args> inline void chkmin(T &d, const Args &...x) { d = Min(d, x...); }

using namespace std;

#ifdef georgeyucjr
#include <georgeyucjr/debug.h>
#else
#define dbg(...) 36
#endif

namespace easy_IO {
inline void read(char &c) { c = getchar(); }
inline void read(string &str, bool is_move = false) { if (is_move) str += ' '; char c = getchar(); while (c != ' ' && c != '\n') str += c, c = getchar(); }
template <typename T> inline void read(T &x, bool is_unsigned = false) { x = 0; char ch = getchar(); if (is_unsigned) { while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar ( ); } else { T _read_flag = (T)(1); while (ch < '0' || ch > '9') _read_flag = ch == '-' ? -1 : 1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar ( ); x *= _read_flag; } return void(); }
template <typename T> inline void read(vector<T> &v) { for (T &i : v) read(v); }
template <typename T, typename... Args> inline void read(T &x, Args&... args) { read(x), read(args...); }
template <typename T, typename U> inline void read(pair<T, U> &p) { read(p.first, p.second); }
template <typename T, typename U, typename V> inline void read(tuple<T, U, V> &t) { read(get<0>(t), get<1>(t), get<2>(t)); }
inline void write ( char c ) { putchar ( c ); }
inline void write ( string s ) { for (char c : s) putchar ( c ); }
template <typename T> inline void write(T x, bool is_unsigned = false) { if (!is_unsigned) if (x < 0) x = -x, putchar ('-'); if (x > 9) write(x / 10); putchar (x % 10 ^ '0'); }
template <typename T> inline void writeln(T x) { write (x), putchar('\n'); }
template <typename T> inline void writespc(T x) { write (x), putchar(' '); }
template <typename T, typename ... Args> inline void write(T x, Args ... args) { write(x), write(args...); }
template <typename T, typename ... Args> inline void writeln(T x, Args ... args) { write(x), putchar(' '), write(args...), putchar('\n'); }
template <typename T, typename ... Args> inline void writespc(T x, Args ... args) { write(x), putchar(' '), write(args...), putchar(' '); }
} // namespace easy_IO
using namespace easy_IO;

# ifndef GY_MMint
# define GY_MMint

namespace georgeyucjr{
namespace internal
{
template <typename T>
struct mkdbwd
{
};
template <>
struct mkdbwd<std ::uint8_t>
{
	using type = std ::uint16_t;
};
template <>
struct mkdbwd<std ::uint16_t>
{
	using type = std ::uint32_t;
};
template <>
struct mkdbwd<std ::uint32_t>
{
	using type = std ::uint64_t;
};
template <>
struct mkdbwd<std ::uint64_t>
{
	using type = unsigned __int128;
};
template <typename T>
using mkdbwd_t = mkdbwd<T>::type;
inline constexpr auto flr(auto &&x, auto &&y)
{
	return x / y - (x % y && (x ^ y) < 0);
}
inline constexpr auto divmod(auto x, auto y)
{
	auto &&q = flr(x, y);
	return std::make_pair(q, x - q * y);
}
} // namespace internal

using namespace internal;
template <typename T>
struct MontgomeryReduction
{
	using int_type = T;
	using int_double_t = mkdbwd_t<T>;
	inline constexpr static int bsw = std::numeric_limits<T>::digits;
	inline constexpr explicit MontgomeryReduction(T mod)
		: _mod(mod),
		  _mod_neg_inv(inv_base(~(mod - 1))),
		  mbs((int_double_t(1) << bsw) % mod),
		  mbs2(int_double_t(mbs) * mbs % mod),
		  mbs3(int_double_t(mbs2) * mbs % mod) {}
	inline constexpr T mod() const { return _mod; }
	inline constexpr T mbase() const { return mbs; }
	inline constexpr T mbase2() const { return mbs2; }
	inline constexpr T mbase3() const { return mbs3; }
	inline constexpr T reduce(int_double_t t) const
	{
		return (t + int_double_t(T(t) * _mod_neg_inv) * _mod) >> bsw;
	}
	inline constexpr T unsafemod(T x) const { return x >= _mod * 2 ? x - _mod * 2 : x; }
	inline constexpr T safemod(T x) const { return x >= _mod ? x - _mod : x; }
	inline constexpr static T inv_base(T x)
	{
		T y = 1;
		for (int i = 1; i < bsw; i <<= 1)
			y *= 2 - x * y;
		return y;
	}

private:
	T _mod, _mod_neg_inv, mbs, mbs2, mbs3;
};
template <std::unsigned_integral T, typename S = std::make_signed_t<T>>
inline constexpr std::tuple<S, S, T> clc(T x, T y)
{
	bool t = x < y;
	if (t)
		swap(x, y);
	if (y == 0)
	{
		if (x == 0)
			return {};
		if (t)
			return {0, 1, x};
		return {1, 0, x};
	}
	S s0 = 1, s1 = 0, t0 = 0, t1 = 1;
	while (true)
	{
		auto [q, r] = divmod(x, y);
		if (r == 0)
		{
			if (t)
				return {t1, s1, y} ;
			return {s1, t1, y};
		}
		S s2 = s0 - S(q) * s1, t2 = t0 - S(q) * t1;
		x = y,
		y = r,
		s0 = s1,
		s1 = s2,
		t0 = t1,
		t1 = t2;
	}
}
template <std::unsigned_integral T>
inline constexpr T modinv(T x, T m)
{
	auto [s, t, g] = clc(x, m);
	assert(g == 1);
	return s < 0 ? T(s) + m : s;
}
template <typename T>
inline constexpr T Qpow(T a, auto b)
{
	T ans{1};
	for (; b; b >>= 1, a *= a)
		if (b & 1)
			ans *= a;
	return ans;
}
template <typename Context>
struct MontgomeryModInt
{
	using mint = MontgomeryModInt;
	using int_type = Context::int_type;
	using mr_type = Context::mr_type;
	using int_double_t = mr_type::int_double_t;
	inline constexpr MontgomeryModInt() = default;
	inline constexpr MontgomeryModInt(long long y)
	{
		using S = std::make_signed_t<int_type>;
		S v = y % S(mod());
		x = mr().reduce(mr().mbase2() * int_double_t(v < 0 ? v + mod() : v));
	}
	inline constexpr MontgomeryModInt(int y)
	{
		using S = std::make_signed_t<int_type>;
		S v = y % S(mod());
		x = mr().reduce(mr().mbase2() * int_double_t(v < 0 ? v + mod() : v));
	}
	inline constexpr MontgomeryModInt(unsigned int y)
	{
		x = mr().reduce(mr().mbase2() * int_double_t(y % mod()));
	}
	inline constexpr MontgomeryModInt(unsigned long long y)
	{
		x = mr().reduce(mr().mbase2() * int_double_t(y % mod()));
	}
	inline constexpr int_type val() const { return mr().safemod(mr().reduce(x)); }
	inline constexpr int_type residue() const { return mr().safemod(x); }
	inline constexpr static int_type mod() { return mr().mod(); }
	inline constexpr mint &operator++()
	{
		x = mr().unsafemod(x + mr().mbase());
		return *this;
	}
	inline constexpr mint operator++(int)
	{
		mint r = *this;
		++*this;
		return r;
	}
	inline constexpr mint &operator+=(const mint &rhs)
	{
		x = mr().unsafemod(x + rhs.x);
		return *this;
	}
	inline constexpr mint &operator--()
	{
		x = mr().unsafemod(x + mod() - mr().mbase());
		return *this;
	}
	inline constexpr mint operator--(int)
	{
		mint r = *this;
		--*this;
		return r;
	}
	inline constexpr mint &operator-=(const mint &rhs)
	{
		x = mr().unsafemod(x + mod() * 2 - rhs.x);
		return *this;
	}
	inline constexpr mint &operator*=(const mint &rhs)
	{
		x = mr().reduce(int_double_t(x) * rhs.x);
		return *this;
	}
	inline constexpr mint inv() const
	{
		return from_raw(
		         mr().reduce(int_double_t(mr().mbase3()) * modinv(x, mod())));
	}
	inline constexpr mint pow(auto n) const { return Qpow(*this, n); }
	inline constexpr mint &operator/=(const mint &rhs) { return *this *= rhs.inv(); }
	inline constexpr mint operator+() const { return *this; }
	inline constexpr mint operator-() const { return from_raw(!x ? 0 : mod() * 2 - x); }
	inline friend constexpr mint operator+(mint lhs, const mint &rhs)
	{
		return lhs += rhs;
	}
	inline friend constexpr mint operator-(mint lhs, const mint &rhs)
	{
		return lhs -= rhs;
	}
	inline friend constexpr mint operator*(mint lhs, const mint &rhs)
	{
		return lhs *= rhs;
	}
	inline friend constexpr mint operator/(mint lhs, const mint &rhs)
	{
		return lhs /= rhs;
	}
	inline friend constexpr bool operator==(const mint &lhs, const mint &rhs)
	{
		return mr().safemod(lhs.x) == mr().safemod(rhs.x);
	}
	inline friend constexpr auto operator<=> (const mint &lhs, const mint &rhs)
	{
		return mr().safemod(lhs.x) <=> mr().safemod(rhs.x);
	}
	inline constexpr static mint from_raw(int_type x)
	{
		mint r;
		r.x = x;
		return r;
	}
	inline constexpr int_type raw() const { return x; }
#ifdef __GEORGEYUCJR_READ__
	inline void write(IO &io) const { io.write(val()); }
#else
	inline friend std::ostream &operator<<(std::ostream &os, const mint &x)
	{
		return os << x.val();
	}
#endif
	inline constexpr static const mr_type &mr()
	{
		return Context::montgomery_reduction();
	}

private:
	int_type x{};
};
template <std::unsigned_integral T, T Mod>
requires(Mod % 2 == 1 && Mod <= std::numeric_limits<T>::max() / 2)
struct StaticMontgomeryReductionContext
{
	using int_type = T;
	using mr_type = MontgomeryReduction<T>;
	constexpr static const mr_type &montgomery_reduction() { return _reduction; }

private:
	constexpr static auto _reduction = mr_type(Mod);
};
template <std::unsigned_integral T>
struct DynamicMontgomeryReductionContext
{
	using int_type = T;
	using mr_type = MontgomeryReduction<T>;
	struct Guard
	{
		Guard(const Guard &) = delete;
		Guard(Guard &&) = delete;
		Guard &operator=(const Guard &) = delete;
		Guard &operator=(Guard &&) = delete;
		~Guard() { _reduction_env.pop_back(); }

	private:
		friend DynamicMontgomeryReductionContext;
		Guard() = default;
	};
	[[nodiscard]] inline static Guard set_mod(T mod)
	{
		assert(mod % 2 == 1 && mod <= std::numeric_limits<T>::max() / 4);
		_reduction_env.emplace_back(mod);
		return {};
	}
	inline constexpr static const mr_type &montgomery_reduction()
	{
		return _reduction_env.back();
	}

private:
	inline static std ::vector<mr_type> _reduction_env;
};

template <std ::uint32_t Mod>
using static_modint = MontgomeryModInt<StaticMontgomeryReductionContext<std ::uint32_t, Mod>>;

template <std ::uint64_t Mod>
using static_modint_64 = MontgomeryModInt<StaticMontgomeryReductionContext<std ::uint64_t, Mod>>;

using modint998244353 = static_modint<998244353>;

using modint1000000007 = static_modint<1000000007>;

#define dymanic_modint_IN(_Tp, Mod)                                      \
    using dymanic_modint_type = DynamicMontgomeryReductionContext<_Tp>; \
    auto _guard = dymanic_modint_type ::set_mod();                      \
    using mint = MontgomeryModInt<dymanic_modint_type>;

#define dymanic_modint(_Tp, Mod)                                      \
    using dymanic_modint_type = georgeyucjr::DynamicMontgomeryReductionContext<_Tp>; \
    auto _guard = dymanic_modint_type ::set_mod(Mod);                      \
    using mint = georgeyucjr::MontgomeryModInt<dymanic_modint_type>;
} // namespace georgeyucjr

# endif

using mint = georgeyucjr :: modint998244353;

signed main() {
	// ios_base ::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int T;
	read(T);
	auto slv = [&]() {
		int n, k;
		string s;
		read(s, k);
		n = SZ(s);
		vector<int> z(n);
		z[0] = n;
		rep(i, 1, n - 1, l = 0, r = 0) {
			z[i] = Max(Min(r - i, z[i - l]), 0);
			while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
			if (i + z[i] > r) l = i, r = i + z[i];
		}
		vector<int> a(n + 1);
		rep(i, 0, n - 1) if (z[i] >= i && 2 * i + k <= n) {
			++a[2 * i + k];
			int x = Min(z[i] - i, n - 2 * i) / k * k + 2 * i;
			if (x + k <= n) --a[x + k];
		}
		mint ans = 1;
		rep(i, 1, n) {
			if (i + k <= n) a[i + k] += a[i];
			ans *= mint(a[i] + 1); 
		}
		writeln(ans.val ());
	};
	while (T--) slv();
#if defined(LOCAL) && !defined(CPH)
	std::cerr << "Spend Time : " << clock() * 1. / CLOCKS_PER_SEC * 1e3 << " ms \n";
#endif
	return 0;
}