#include <bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
#define pil pair<int,ll>
#define fi first
#define se second

const int N=5e5+5;

int T,n,top,hd,tl;
int nxt[N],bor[N];
ll m;
ll dis[N],tmp[N];
pil q[N];
char s[N];

il void Nxt(){
	top=0;
	for(int i=2,j=0;i<=n;i++){
		while(j&&s[i]!=s[j+1])j=nxt[j];
		if(s[i]==s[j+1])++j;
		nxt[i]=j;
	}
	int p=n;
	do p=nxt[p],bor[++top]=n-p;
	while(p);
	return ;
}

il int Add(int x,int y,int mod){return x+y>=mod?x+y-mod:x+y;}

il void Update(int fir,int del,int len,int mod){
	int d=__gcd(del,mod);
	for(int t=0;t<d;t++){
		int pos=-1,p=t,c;ll mn=m+1;
		do{
			p=Add(p,del,mod);
			if(dis[p]<mn)mn=dis[p],pos=p;
		}while(p^t);
		if(pos==-1)continue;
		hd=1,tl=0,p=pos,c=0;
		q[++tl]={0,mn};
		do{
			p=Add(p,del,mod),c++;
			while(hd<=tl&&c-q[hd].fi>len)++hd;
			dis[p]=min(dis[p],q[hd].se+(ll)(c-q[hd].fi)*del+fir);
			while(hd<=tl&&q[tl].se+(ll)(c-q[tl].fi)*del>dis[p])--tl;
			q[++tl]={c,dis[p]};
		}while(p^pos);
	}
	return ;
}

il void Build(){
	cin>>n>>m>>(s+1);
	Nxt();
	for(int i=0;i<bor[1];i++)dis[i]=m+1;
	dis[n%bor[1]]=n;
	int lst=1;
	for(int i=1,j=0;i<top;i=j+1){
		int del=bor[i+1]-bor[i];
		j=i;
		while(j<top&&bor[j+1]-bor[j]==del)++j;
		if(j>i)Update(bor[i],del,j-i,bor[i]),lst=i;
		if(j<top){
			for(int k=0;k<bor[j+1];k++)tmp[k]=m+1;
			for(int k=0;k<bor[i];k++){
				ll p=dis[k]%bor[j+1];
				tmp[p]=min(tmp[p],dis[k]);
			}
			swap(dis,tmp);
			Update(0,bor[i],1,bor[j+1]),lst=j+1;
		}
	}
	ll ans=0;
	for(int i=0;i<bor[lst];i++){
		if(dis[i]<=m)ans+=(m-dis[i])/bor[lst]+1;
	}
	cout<<ans<<"\n";
	return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--)Build();
	return 0;
}