#include <algorithm>
#include <iostream>
#include <tuple>
using ll=long long;
constexpr ll inf(1.01e18);
constexpr int N(5e5+10);
void trans(ll mn[],int &q,int p,int d,int c)
{
	static ll b[N];std::fill(b,b+p,inf);
	for(int i(0),j;i<q;++i) j=mn[i]%p,b[j]=std::min(b[j],mn[i]);
	{
		int t(std::__gcd(p,q)),r(q%p);
		for(int i(0);i<t;++i)
		{
			ll mt(inf);int pt(0),s(i);
			do
			{
				if(b[s]<mt)	mt=b[s],pt=s;
				s+=r;if(s>=p) s-=p;
			}while(s!=i);
			mt=inf;s=pt;
			do
			{
				mt=std::min(mt+q,b[s]);
				b[s]=mt;s+=r;if(s>=p) s-=p;
			}while(s!=pt);
		}
	}
	{
		int t(std::__gcd(p,d)),r(d%p);
		for(int i(0);i<t;++i)
		{
			ll mt(inf);int pt(0),s(i);
			do
			{
				if(b[s]<mt) mt=b[s],pt=s;
				s+=r;if(s>=p) s-=p;
			}while(s!=i);
			struct _q
			{
				ll val;int pos;
			};static _q qq[N];int ql(0),qr(0);
			s=pt;int k(0);
			do
			{
				++k;if(ql<qr) b[s]=std::min(b[s],qq[ql].val+1ll*k*d+p);
				ll val(b[s]-1ll*k*d);
				while(ql<qr && qq[qr-1].val>=val) --qr;qq[qr++]=(_q){val,k};
				while(ql<qr && qq[ql].pos<=k-c) ++ql;
				s+=r;if(s>=p) s-=p;
			}while(s!=pt);
		}
	}
	std::copy(b,b+p,mn);q=p;
}
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int T;std::cin>>T;
	while(T--)
	{
		static std::tuple<int,int,int> ds[20];int cnt(0);static int fl[N];
		int n;ll x;static char s[N];std::cin>>n>>x>>(s+1);
		for(int i(2);i<=n;++i)
		{
			int j(fl[i-1]);while(j && s[j+1]!=s[i]) j=fl[j];
			if(s[j+1]==s[i]) ++j;fl[i]=j;
		}
		for(int i(fl[n]);i;)
		{
			int j(i),k(1);
			for(;fl[j]>i/2;j=fl[j],++k);
			if(k==1) ds[++cnt]={n-i,1,0};
			else ds[++cnt]={n-i,(i-j)/(k-1),k-1};
			i=fl[j];
		}
		static ll mn[N];int cur(n);std::fill(mn,mn+n,inf);mn[0]=n;
		for(int i(1);i<=cnt;++i)
		{
			auto [m,d,c]=ds[i];
			// std::cerr<<m<<" "<<d<<" "<<c<<std::endl;
			trans(mn,cur,m,d,c);
			// for(int i(0);i<cur;++i) std::cerr<<mn[i]<<" ";std::cerr<<std::endl;
		}
		long long ans(0);
		for(int i(0);i<cur;++i) if(mn[i]<=x) ans+=(x-mn[i])/cur+1;
		std::cout<<ans<<"\n";
	}
	return 0;
}