#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=5e5+10;
const ll llinf=0x3f3f3f3f3f3f3f3f;

inline ll read(){
    ll x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}

int gcd(int A,int B){
    if(!B) return A;
    return gcd(B,A%B);
}

int t;
int n;
ll w;
char s[maxn];
int nxt[maxn];
bool vis[maxn];
struct Border{
    int A,D,L;
    Border()=default;
    Border(int A_,int D_,int L_):A(A_),D(D_),L(L_){}
};
vector<Border> V;
inline void get_nxt(){
    for(int i=1;i<=n;++i) vis[i]=false;
    nxt[1]=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;
    }
    V.clear();
    // for(int i=1;i<=n;++i) cerr<<nxt[i]<<" ";
    // cerr<<endl;
    int p=nxt[n];
    while(p){
        int q=p;
        while(p-nxt[p]==q-nxt[q]) q=nxt[q];
        V.push_back(Border(n-p,p-nxt[p],(p-q)/(p-nxt[p])-1));
        p=q;
    }
}

ll f[maxn];
int id[maxn];
int q[maxn],head,tail;
inline void solve1(int A,int D,int L){
    int d=gcd(A,D);
    for(int k=0;k<d;++k){
        ll mn=llinf;
        int x=k;
        do{
            mn=min(mn,f[x]);
            x=(x+D)%A;
        }while(x!=k);
        do{
            if(mn==f[x]){
                int i=x,j=0;
                do{
                    id[j++]=i;
                    i=(i+D)%A;
                }while(i!=x);
                break;
            }
            x=(x+D)%A;
        }while(x!=k);
        head=1,tail=0;
        for(int i=0;i<A/d;++i){
            while(head<=tail&&i-q[head]>L) ++head;
            if(head<=tail) f[id[i]]=min(f[id[i]],f[id[q[head]]]+1ll*(i-q[head])*D+A);
            while(head<=tail&&f[id[q[tail]]]-1ll*q[tail]*D>=f[id[i]]-1ll*i*D) --tail;
            q[++tail]=i;
        }
    }
}
ll g[maxn];
inline void solve2(int A1,int A2){
    for(int i=0;i<A2;++i) g[i]=llinf;
    for(int i=0;i<A1;++i){
        if(f[i]==llinf) continue;
        g[f[i]%A2]=min(g[f[i]%A2],f[i]);
    }
    for(int i=0;i<A2;++i) f[i]=llinf;
    int d=gcd(A1,A2);
    for(int k=0;k<d;++k){
        ll mn=llinf;
        int x=k;
        do{
            mn=min(mn,g[x]);
            x=(x+A1)%A2;
        }while(x!=k);
        do{
            if(mn==g[x]){
                int i=x,j=0;
                do{
                    id[j++]=i;
                    i=(i+A1)%A2;
                }while(i!=x);
                break;
            }
            x=(x+A1)%A2;
        }while(x!=k);
        mn=llinf;
        for(int i=0;i<A2/d;++i){
            mn=min(mn,g[id[i]]-1ll*i*A1);
            f[id[i]]=mn+1ll*i*A1;
        }
    }
}

int main(){
    t=read();
    while(t--){
        n=read(),w=read();
        scanf("%s",s+1);
        get_nxt();
        f[0]=0;
        for(int i=1;i<n;++i) f[i]=llinf;
        int lastA=n;
        for(Border b:V){
            solve2(lastA,b.A);
            // cerr<<"("<<b.A<<","<<b.D<<","<<b.L<<")"<<endl;
            // for(int i=0;i<b.A;++i) cerr<<f[i]<<" ";
            // cerr<<endl;
            solve1(b.A,b.D,b.L);
            // for(int i=0;i<b.A;++i) cerr<<f[i]<<" ";
            // cerr<<endl;
            lastA=b.A;
        }
        if(w<n) printf("0\n");
        else{
            w-=n;
            ll ans=0;
            for(int i=0;i<lastA;++i){
                if(w>=f[i]) ans+=(w-f[i])/lastA+1;
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}