#include<bits/stdc++.h>

#define pii pair<int,int>
#define maxn 500005
#define int long long
#define INF 4557430888798830399

using namespace std;

inline int read(){
    int lre=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-'){
            f=-1;
        }
        c=getchar();
    }
    while(isdigit(c)){
        lre=(lre<<3)+(lre<<1)+(c-'0');
        c=getchar();
    }
    return lre*f;
}

int n,w;
string str;
int kmp[maxn];
int m;
int a[maxn];//周期,最后求的就是他们的线性组合 
int f[maxn],g[maxn];

int l,r;
int q[maxn],ind[maxn];
int pos[maxn];

void show_arr(string name,int arr[],int l,int r){
	cout<<name<<":"; 
	for(int i=l;i<=r;i++){
		if(arr[i]==INF)cout<<"inf ";
		else cout<<arr[i]<<" ";
	}
	cout<<endl;
}

bool cmp(int a,int b){
	return f[a]<f[b];
}

void trans(int m1,int m2){
	if(m1==-1)return;
	memset(g,0x3f,sizeof(g));
	for(int i=0;i<m1;i++){
		g[f[i]%m2]=min(g[f[i]%m2],f[i]);
	}
	for(int i=0;i<m2;i++){
		f[i]=g[i];//再用f[i]+k*m1更新 
		ind[i]=i;
	}
	memset(pos,0,sizeof(pos));
	sort(ind,ind+m2,cmp);
	for(int i=0;i<m2;i++){
		if(pos[ind[i]])continue;
		int id=1,x=ind[i];
		l=1,r=0;
		do{	
			pos[x]=id++;
			while(r>=l&&f[x]-pos[x]*m1<=f[q[r]]-pos[q[r]]*m1)r--;
			q[++r]=x;
			f[x]=f[q[l]]+(pos[x]-pos[q[l]])*m1;
			x=(x+m1)%m2;
		}while(!pos[x]);
	}
}//换模 

void calc(int d,int lim,int mod){
	for(int i=0;i<mod;i++){
		ind[i]=i;
	}
	memset(pos,0,sizeof(pos));
	sort(ind,ind+mod,cmp);
	for(int i=0;i<mod;i++){
		int x=ind[i];
		if(pos[x])continue;
		int id=1;
		l=1,r=0;
		do{
			pos[x]=id++;
			while(r>=l&&pos[x]-pos[q[l]]>lim)l++;
			while(r>=l&&f[x]-pos[x]*d<=f[q[r]]-pos[q[r]]*d)r--;
			q[++r]=x;
			f[x]=min(f[x],f[q[l]]+(pos[x]-pos[q[l]])*d+mod);
			x=(x+d)%mod;
		}while(!pos[x]);
	} 
}//环上转移(公差,长度限制,什么意义下取模) 

void solve(){
	n=read();w=read();
	cin>>str;str=' '+str;
	for(int i=2;i<=n;i++){
		int j=kmp[i-1];
		while(j&&str[j+1]!=str[i]){
			j=kmp[j];
		}
		if(str[j+1]==str[i])j++;
		kmp[i]=j;
	}
	int j=n;m=0;
	while(j){
		j=kmp[j];
		a[++m]=n-j;
	}
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	
//	show_arr("a",a,1,m);
	
	int lst=-1;
	int pre=1,nxt;
	while(pre<=m){
		nxt=pre+1;
		while(a[nxt]-a[nxt-1]==a[nxt+1]-a[nxt]&&nxt!=m)nxt++;
		nxt=min(nxt,m);
		//[pre,nxt]之间
		if(lst!=-1){
			trans(lst,a[pre]);
		} 
	//	cout<<"solve ["<<pre<<","<<nxt<<"]"<<endl;
		if(nxt>pre)calc(a[pre+1]-a[pre],nxt-pre,a[pre]);
	//	show_arr("f",f,0,a[pre]-1);
		lst=a[pre];pre=nxt+1;
	}
//	cout<<"lst="<<lst<<endl;
	int res=0;
	for(int i=0;i<lst;i++){
	//	cout<<"i="<<i<<" dis="<<f[i]<<endl;
		if(f[i]<=w-n){
			res+=(w-n-f[i])/lst+1;
		}
	}
	printf("%lld\n",res);
}

signed main(){
	int T=read();
	while(T--){
		solve();
	}
	return 0;
}
/*
1
9 100
abaabbaba
82
*/