// 那就是希望。
// 即便需要取模，也是光明。

#ifndef MYEE
#pragma GCC optimize("Ofast")
#endif

#include <algorithm>
#include <random>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
// Heaven and Earth... My guiding star...
chr C[500005];uint Nxt[500005],n;
ullt Dist[500005],User[500005];
ullt hash,Ans,w0;
std::mt19937 rng(114514);
ullt T[26];
voi solve()
{
    ullt w;scanf("%u%llu%s",&n,&w,C),Nxt[0]=-1;
    if(w<n){puts("0");return;}
    w-=n;
    ullt h=0;for(uint i=0;i<n;i++)h=(h*114514+T[C[i]-'a'])%998244353;
    if(h==hash&&w0==w){printf("%llu\n",Ans);return;}
    hash=h,w0=w;
    for(uint i=1,j=-1;i<n;i++)
    {
        while(~j&&C[j+1]!=C[i])j=Nxt[j];
        if(C[j+1]==C[i])j++;
        Nxt[i]=j;
    }
    std::vector<uint>R;
    for(uint i=n-1;~i;)R.push_back(n-1-(i=Nxt[i]));
    uint g=0;
    for(uint p=0,r;p<R.size();p=r)
    {
        r=p+1;while(r<R.size()&&R[r]-R[r-1]==R[p+1]-R[p])r++;
        if(r+1<R.size()&&R[r]-R[r-1]==R[r+1]-R[r])r--;
        // if(r==p+2&&r+1<R.size()&&R[r]-R[r-1]==R[r+1]-R[r])r--;
        // if(r-p<=2)r=p+1;
        uint l=R[p],k=r-p;
        for(uint i=0;i<g;i++)User[i]=Dist[i];
        for(uint i=1;i<l;i++)Dist[i]=1e18;
        for(uint i=0;i<g;i++)_min(Dist[User[i]%l],User[i]);
        for(uint i=gcd(g,l)-1;~i;i--)
        {
            uint j=i;
            do _min(Dist[(j+g)%l],Dist[j]+g),j=(j+g)%l;while(j!=i);
            do _min(Dist[(j+g)%l],Dist[j]+g),j=(j+g)%l;while(j!=i);
        }
        g=l;if(k==1)continue;
        uint d=R[p+1]-R[p];if(!(d%g))continue;
        _min(k,g/gcd(g,d));
        for(uint i=gcd(g,d)-1;~i;i--)
        {
            static uint V[500005],tp;V[0]=i,tp=1;
            while((V[tp]=(V[tp-1]+d)%g)!=i)tp++;
            uint t=0;
            if(i)for(uint j=1;j<tp;j++)if(Dist[V[j]]<Dist[V[t]])t=j;
            for(uint j=0;j<t;j++)V[tp+j]=V[j];
            static uint D[500005],bgn,end;bgn=end=0;
            for(uint j=t;j<t+tp;j++)
            {
                if(bgn<end&&j-D[bgn]==k)bgn++;
                if(bgn<end)_min(Dist[V[j]],Dist[V[D[bgn]]]+g+(ullt)d*(j-D[bgn]));
                while(bgn<end&&Dist[V[j]]<=Dist[V[D[end-1]]]+(ullt)d*(j-D[end-1]))end--;
                D[end++]=j;
            }
        }
    }
    ullt ans=0;
    for(uint i=0;i<g;i++)if(Dist[i]<=w)ans+=(w-Dist[i])/g+1;
    printf("%llu\n",Ans=ans);
}
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    freopen("QAQ.out","w",stdout);
#endif
    for(uint i=0;i<26;i++)T[i]=rng();
    uint t;scanf("%u",&t);
    while(t--)solve();
    return 0;
}

// 那就是希望。
// 即便需要取模，也是光明。