#include<cstdio>
#include<cstring>
namespace IO{
	const int ARR_SIZE=1<<20;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
	void getstr(char*str){
		char ch=gc();
		while(ch=='\r'||ch=='\n'||ch==' '||ch=='\t')ch=gc();
		while(ch!='\r'&&ch!='\n'&&ch!=' '&&ch!='\t'&&ch!=EOF)*(str++)=ch,ch=gc();
		*str='\0';
	}
	template<typename T>
	void write(T a){
		static int ch[50],cnt=0;
		if(a==0)pc('0');
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
}
using IO::read;
using IO::getstr;
using IO::write;
template<typename T>
inline T gcd(T a,T b){
	while(b){
		a%=b;
		a^=b^=a^=b;
	}
	return a;
}
template<typename T>
inline void chkmin(T&a,const T b){
	a>b&&(a=b);
}
inline int qmod(const int x,const int P){
	return x>=P?x-P:x;
}
typedef long long ll;
const int maxn=500000;
int n;
ll w;
char s[maxn+2];
int fail[maxn+1],stack[maxn+1],top;
ll f[maxn],g[maxn];
struct Data{
	int pos;
	ll val;
}q[maxn+1];
int l,r;
void getFail(){
	fail[1]=0;
	for(int i=2,j;i<=n;i++){
		j=fail[i-1];
		while(j&&s[j+1]!=s[i])j=fail[j];
		if(s[j+1]==s[i])j++;
		fail[i]=j;
	}
	top=0;
	for(int now=n;now;)stack[++top]=n-(now=fail[now]);
}
void trans(const int P,const int a0,const int d,const int lim){
	const int g=gcd(P,d);
	for(int T=0;T<g;T++){
		ll mn=f[T];
		int pos=T;
		for(int j=qmod(T+d,P);j!=T;j=qmod(j+d,P))
			if(mn>f[j])
				mn=f[j],pos=j;
		if(mn==w+1)continue;
		if(lim==1)
			for(int j=qmod(pos+d,P),k=pos;j!=pos;){
				chkmin(f[j],f[k]+d+a0);
				k=j,j=qmod(j+d,P);
			}
		else{
			l=1,r=0;
			q[++r]=Data{0,mn};
			for(int i=1,j=qmod(pos+d,P);j!=pos;i++){
				while(l<=r&&i-q[l].pos>lim)l++;
				chkmin(f[j],q[l].val+ll(i-q[l].pos)*d+a0);
				while(l<=r&&q[r].val-f[j]>ll(q[r].pos-i)*d)r--;
				q[++r]=Data{i,f[j]};
				j=qmod(j+d,P);
			}
		}
	}
}
void solve(){
	read(n),read(w);
	getstr(s+1);
	getFail();
	int res=1;
	for(int k=0;k<stack[res];k++)f[k]=w+1;
	f[n%stack[res]]=n;
	for(int i=1,j,diff;i<top;i=j+1){
		j=i+1,diff=stack[j]-stack[j-1];
		while(j<top&&stack[j+1]-stack[j]==diff)j++;
		trans(stack[i],stack[i],diff%stack[i],j-i),res=i;
		if(j<top){
			for(int k=0;k<stack[j+1];k++)g[k]=w+1;
			for(int k=0;k<stack[i];k++)chkmin(g[f[k]%stack[j+1]],f[k]);
			memcpy(f,g,sizeof(ll)*stack[j+1]);
			trans(stack[j+1],0,stack[i],1),res=j+1;
		}
	}
	ll ans=0;
	for(int i=0;i<stack[res];i++)
		if(f[i]<=w)
			ans+=(w-f[i])/stack[res]+1;
	write(ans),pc('\n');
}
int main(){
	int T;
	read(T);
	while(T--)solve();
	return 0;
}