#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 500010
#define inf (1e18+10)
ll n,w;
string s;
ll nxt[N];
ll cn=0,x[N],d[N],l[N];
ll ans[N];
ll nw[N];
bool vis[N];
ll xu[N];
#define T pair<ll,ll>
#define fi first
#define se second
#define mk make_pair
T q[N];
ll ql=1,qr=0;
inline void solve(ll x,ll y,ll z,ll f){
	memset(vis,0,sizeof(vis));
	for(int i=0;i<x;i++){
		if(vis[i])continue;
		vector<ll>tem;ll cnt=0;tem.push_back(i);vis[i]=1;
		for(int j=(i+y)%x;j!=i;j=(j+y)%x)tem.push_back(j),vis[j]=1;
		ll pos=0;for(int j=1;j<tem.size();j++)if(ans[tem[j]]<ans[tem[pos]])pos=j;
		for(int j=pos;j<tem.size();j++)xu[++cnt]=tem[j];for(int j=0;j<pos;j++)xu[++cnt]=tem[j];
		ql=1;qr=0;q[++qr]=mk(1,ans[xu[1]]-y+f);
		for(int j=2;j<=cnt;j++){
			while(j-q[ql].fi>z&&ql<=qr)ql++;
			ans[xu[j]]=min(ans[xu[j]],y*j+q[ql].se);
			while(q[qr].se>=ans[xu[j]]-y*j+f&&ql<=qr)qr--;
			q[++qr]=mk(j,ans[xu[j]]-y*j+f);
		}/*ql=1,qr=0;q[++qr]=mk(cnt+1,ans[xu[1]]+(cnt+1)*y);
		for(int j=cnt;j>=2;j--){
			while(q[ql].fi-j>z&&ql<=qr)ql++;
			while(q[qr].se>=ans[xu[j]]+j*y&&ql<=qr)qr--;
			q[++qr]=mk(j,ans[xu[j]]+y*j);
			ans[xu[j]]=min(ans[xu[j]],y*j+q[ql].se); 
		}*/
	}
	return ;
}
int main()
{
//	freopen("test1.in","r",stdin);
	//freopen(".in","r",stdin);
	//freopen("test1.out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	ll ti;cin>>ti;while(ti--){
		cn=0;cin>>n>>w>>s;nxt[0]=-1;
		if(w<n){cout<<0<<'\n';continue;}w-=n;
		for(int i=1;i<n;i++){
			ll o=nxt[i-1];
			while(o!=-1&&s[o+1]!=s[i])o=nxt[o];
			if(s[o+1]==s[i])o++;nxt[i]=o;
		}vector<ll>tem;ll nww=nxt[n-1];while(nww!=-1)tem.push_back(n-nww-1),nww=nxt[nww];
		tem.push_back(n);sort(tem.begin(),tem.end());
		x[++cn]=tem[0];l[cn]=d[cn]=0;for(int i=1;i<tem.size();i++){
			ll o=tem[i];
			if(!d[cn])d[cn]=o-x[cn],l[cn]=1;
			else{
				if(d[cn]==o-tem[i-1])l[cn]++;
				else{
					x[++cn]=o;d[cn]=l[cn]=0;
				}
			}
		}for(int i=0;i<n;i++)ans[i]=inf;ans[0]=0;
		for(int i=1;i<=cn;i++){
			if(x[i-1]){
				ll o=x[i-1];
				for(int j=0;j<x[i];j++)nw[j]=inf;
				for(int j=0;j<x[i-1];j++)nw[ans[j]%x[i]]=min(ans[j],nw[ans[j]%x[i]]);
				for(int j=0;j<x[i];j++)ans[j]=nw[j];
				solve(x[i],x[i-1],inf,0);
			}solve(x[i],d[i],l[i],x[i]);
		}ll an=0;
		for(int i=0;i<x[cn];i++){
			if(ans[i]<=w)an+=(w-ans[i])/x[cn]+1;
		}cout<<an<<'\n';
	}
	return 0;
}