// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 5e5 + 5, INF = 1e9;

char s[N];

int nxt[N], n;
LL w;

void inline KMP() {
	for (int i = 2, j = 0; i <= n; i++) {
		while (j && s[j + 1] != s[i]) j = nxt[j];
		if (s[j + 1] == s[i]) ++j;
		nxt[i] = j;
	}
}

struct DSU{
	int f[N];
	void inline init() {
		for (int i = 0; i <= n + 1; i++) f[i] = i;
	}
	int find(int x) {
		return x == f[x] ? x : f[x] = find(f[x]);
	}
} t[12][2];

int d[N];

int c[N], tot;

int len, A[N], B[N], W[N];

void inline work() {
	int p = nxt[n];
	tot = 0;
	while (p) {
		c[++tot] = n - p;
		p = nxt[p];
	}
	len = 0;
	for (int i = 1; i <= tot; i++) {
		if (i == tot) {
			++len;
			A[len] = c[i];
			B[len] = 1;
			W[len] = 0;
		} else {
			int j = i + 1;
			while (j < tot && c[j + 1] - c[j] == c[i + 1] - c[i]) j++;
			++len;
			A[len] = c[i];
			B[len] = c[i + 1] - c[i];
			W[len] = j - i;
			i = j;
		}
	}
}

int q[N << 1];

bool vis[N];

void inline bfs() {
	for (int i = 0; i < n; i++) d[i] = INF, vis[i] = 0;
	d[0] = 1;
	for (int i = 1; i <= len; i++)
		t[i][0].init(), t[i][1].init();
	int hh = N, tt = N;
	q[N] = 0;
	while (hh <= tt) {
		int u = q[hh++];
		if (vis[u]) continue;
		vis[u] = 1;
		for (int i = 1; i <= len; i++) {
			int rt = u + A[i] + B[i] * W[i];
			int r0 = min(n - 1, rt);
			if (u + A[i] <= n) {
				for (int v = t[i][0].find(u + A[i]); v <= r0; v = t[i][0].find(v)) {
					if (d[u] < d[v]) {
						d[v] = d[u], q[--hh] = v;
					}
					t[i][0].f[v] = min(v + B[i], n + 1);
				}
			}
			if (rt > n) {
				rt -= n;
				int loc = u + A[i];
				if (loc > n) loc -= n;
				else loc = W[i] == 0 ? rt : rt % B[i];
				for (int v = t[i][1].find(loc); v <= rt; v = t[i][1].find(v)) {
					if (d[u] + 1 < d[v]) {
						d[v] = d[u] + 1, q[++tt] = v;
					}
					t[i][1].f[v] = min(v + B[i], n + 1);
				}
			}
		}
	}
}

int ln;
LL lw, la;

char ls[N];

void inline out() {
	LL ans = 0;
	for (int i = 0; i < n; i++) {
		int v = d[i];
		if (v != INF) {
			LL st = 1ll * v * n + i;
			if (st <= w) ans += (w - st) / n + 1;
		}
	}
	la = ans;
	ln = n, lw = w;
	for (int i = 1; i <= n; i++) ls[i] = s[i];
	printf("%lld\n", ans);
}

bool inline chk() {
	if (ln != n || lw != w) return 0;
	for (int i = 1; i <= n; i++) if (s[i] != ls[i]) return 0;
	return 1; 
}

int main() {
	//freopen("ex_jie3.in", "r", stdin);
	int T; read(T);
	while (T--) {
		read(n); read(w);
		scanf("%s", s + 1);
		if (chk()) {
			printf("%lld\n", la);
			continue;
		}
		KMP();
		work();
		bfs();
		out();
	}	
    return 0;
}