#include <bits/stdc++.h>
#define _for(i, a, b) for (int i = a; i <= b; ++i)
#define for_(i, a, b) for (int i = a; i >= b; --i)
#define far(i, vec) for (auto i : vec)
#define bdmd int mid = (l + r) >> 1
typedef long double ldb;
typedef long long ll;
typedef double db;
typedef std::pair <int, int> pii;
typedef std::pair <ll, ll> pll;
const int N = 5e5 + 10, P = 998244353;
namespace IO {
	ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
} // namespace IO
namespace SOLVE {
	using namespace IO;
	ll n, w, fail[N], F[N], G[N], ans;
	char S[N];
	std::vector <int> len;
	bool vis[N];
	ll laa, que[N][2], hd, tl;
	void Upd (int a, int d, int c) {
		assert (laa >= -1);
		if (laa != -1) {
			_for (i, 0, a - 1) G[i] = w + 1;
			_for (i, 0, a - 1) if (F[i] <= w)
				G[F[i] % a] = std::min (G[F[i] % a], F[i]);
			_for (i, 0, a - 1) F[i] = G[i];
			_for (i, 0, a - 1) vis[i] = false;
			_for (i, 0, a - 1) if (!vis[i]) {
				std::vector <int> cir;
				ll p = i, minp = p;
				do {
					if (F[minp] > F[p]) minp = p;
					cir.emplace_back (p), vis[p] = true;
					p = (p + laa) % a;
				} while (p != i);
				int siz = cir.size ();
				_for (j, 0, siz - 1)
					if (cir[j] == minp) {
						minp = j;
						break;
					}
				_for (j, 1, siz - 1) {
					int u = (minp + j) % siz, v = (u + siz - 1) % siz;
					F[cir[u]] = std::min (F[cir[u]], F[cir[v]] + laa);
				}
			}
		}
		_for (i, 0, a - 1)
			vis[i] = false;
		_for (i, 0, a - 1) if (!vis[i]) {
			std::vector <int> cir;
			ll p = i, minp = p;
			do {
				if (F[minp] > F[p]) minp = p;
				cir.emplace_back (p), vis[p] = true;
				p = (p + d) % a;
			} while (p != i);
			int siz = cir.size ();
			hd = 1, tl = 0;
			_for (j, 0, siz - 1)
				if (cir[j] == minp) {
					minp = j;
					break;
				}
			_for (j, 0, siz - 1) {
				int u = (minp + j) % siz;
				while (hd <= tl && que[hd][0] <= j - c)
					++hd;
				if (hd <= tl) {
					int v = (minp + que[hd][0]) % siz;
					ll w = (j - que[hd][0]) * d + a;
					F[cir[u]] = std::min (F[cir[u]], que[hd][1] + w);
				}
				while (hd <= tl) {
					int v = (minp + que[tl][0]) % siz;
					if (que[tl][1] + (j - que[tl][0]) * d < F[cir[u]])
						break;
					--tl;
				}
				if (F[cir[u]] <= w)
					++tl, que[tl][0] = j, que[tl][1] = F[cir[u]];
			}
		}
		laa = a;
		return;
	}
	void In () {
		n = rnt (), w = rnt ();
		scanf ("%s", S + 1);
		return;
	}
	void Solve () {
		fail[1] = 0;
		_for (i, 2, n) {
			fail[i] = fail[i - 1];
			while (fail[i] && S[fail[i] + 1] != S[i])
				fail[i] = fail[fail[i]];
			if (S[fail[i] + 1] == S[i])
				++fail[i];
		}
		int k = fail[n];
		std::vector <int> ().swap (len);
		while (k)
			len.emplace_back (n - k), k = fail[k];
		std::reverse (len.begin (), len.end ());
		_for (i, 1, n) F[i] = w + 1;
		F[0] = 0, ans = 0, laa = -1;
		int siz = len.size ();
		std::stack <std::array<int, 3> > U;
		if (siz) {
			int a = len[0], d = 0, c = 1;
			_for (i, 1, siz - 1) {
				if (d == 0)
					d = a - len[i];
				else if (a - len[i] != d)
					U.push ({ a, d, c }), d = 0, c = 0;
				++c, a = len[i];
			}
			Upd (a, d, c);
			while (!U.empty ())
				Upd (U.top ()[0], U.top ()[1], U.top ()[2]), U.pop ();
		}
		Upd (n, 0, 1);
		_for (i, 0, n - 1) if (F[i] + n <= w)
			ans += (w - F[i]) / n;
		return;
	}
	void Out () {
		printf ("%lld\n", ans);
		return;
	}
}
int main () {
	int T = IO::rnt ();
	while (T--) {
		SOLVE::In ();
		SOLVE::Solve ();
		SOLVE::Out ();
	}
	return 0;
} /*

*/