#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dou;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mapa make_pair
typedef long double ld;
typedef unsigned long long ull;
#define ep emplace_back
template <typename T>inline void read(T &x){
	x=0;char c=getchar();bool f=0;
	for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+(c^48);
	x=(f?-x:x);
}
const int N=5e5+5;
int T, n; ll w;
char s[N];
int nxt[N];
int p[N], m;
void kmp(){
	m=0;
	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;
	}
	for(int i=nxt[n]; i; i=nxt[i]) p[++m]=n-i;
	p[++m]=n;
}
ll dis[N], tem[N];
int lstmod;
pair<int, ll> que[N];
void work(int pos, int st, int dt, int len){
	int curmod=p[pos], d=__gcd(dt, curmod);
	lstmod=curmod;
	for(int i=0; i<d; ++i){
		int it=i;
		for(int j=(i+dt)%curmod; j!=i; j=(j+dt)%curmod){
			if(dis[j]<dis[it]) it=j;
		}
		int l=1, r=1;
		que[r]=mapa(0, dis[it]);
		for(int j=(it+dt)%curmod, k=1; j!=it; j=(j+dt)%curmod, ++k){
			while(l<=r&&k-que[l].fi>len) ++l;
			dis[j]=min(dis[j], que[l].se+1ll*(k-que[l].fi)*dt+st);
			while(l<=r&&que[r].se+1ll*(k-que[r].fi)*dt>=dis[j]) --r;
			que[++r]=mapa(k, dis[j]);
		}
	}
}
void solve(){
	read(n); read(w);
	scanf("%s", s+1);
	kmp();
	for(int i=0; i<p[1]; ++i) dis[i]=w+1;
	lstmod=p[1];
	dis[n%p[1]]=n;
	for(int l=1, r; l<m; l=r+1){
		r=l+1;
		while(r<=m&&p[r]-p[r-1]==p[l+1]-p[l]) ++r;
		--r;
		if(l!=r) work(l, p[l], p[l+1]-p[l], r-l);
		if(r!=m){
			for(int i=0; i<p[r+1]; ++i) tem[i]=w+1;
			for(int i=0; i<p[l]; ++i) tem[dis[i]%p[r+1]]=min(tem[dis[i]%p[r+1]], dis[i]);
			for(int i=0; i<p[r+1]; ++i) dis[i]=tem[i];
			work(r+1, 0, p[l], 1);
		}
	}
	ll ans=0;
	for(int i=0; i<lstmod; ++i) if(dis[i]<=w) ans+=(w-dis[i])/lstmod+1;
	printf("%lld\n", ans);
}
int main(){
	// freopen("D:\\nya\\acm\\A\\test.in","r",stdin);
	// freopen("D:\\nya\\acm\\A\\test.out","w",stdout);
	read(T);
	while(T--) solve();
	return 0;
}