#include<bits/stdc++.h>
#define int long long
#define For(i, a, b) for(int i = (a); i <= (b); ++i)
#define Rof(i, a, b) for(register int i = (a); i >= (b); --i)
#define For_Sub(T, S) for(register int T = S; T; T = (T - 1) & T)
#define For_Edge(i, x) for(auto i : edge[x])
#define For_Mul(i, a, b) for(register int i = (a); i <= (b); i += (a))
#define pii pair <int, int>
#define fi first
#define se second
#define eb push_back
#define mp make_pair
#define Size(a) ((int)a.size())
#define All_Vec(a) a.begin(), a.end()
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
inline void Checkmin(int &x, int y) { x = x < y ? x : y; }
inline void Checkmax(int &x, int y) { x = x > y ? x : y; }
const int maxn = 5 * 1e5 + 5, INF = 2e18 + 7;
int T, n, m, W, mod, Cntlen, Answer;
char S[maxn]; int Fail[maxn], Period[maxn], Cnt[maxn], f[maxn], Dis[maxn], Que[maxn];
inline void KMP() {
    Fail[1] = 0, Fail[0] = -1;
    int j;
    For(i, 2, n) {
        j = Fail[i - 1];
        while(j != -1 && S[j + 1] != S[i]) j = Fail[j];
        Fail[i] = ++j;
    }
    j = Fail[n];
    while(j != -1) {
        Period[++m] = n - j;
        j = Fail[j];
    }
}
inline void DP1(int p, int d, int len) {
    int pos = -1, i = p; Cntlen = 0;
    do {
        if(pos == -1 || Dis[pos] > Dis[i]) pos = i;
        i = (i + d) % mod;
    }while(i != p);
    i = pos;
    do {
        Cnt[++Cntlen] = i, i = (i + d) % mod;
    }while(i != pos);
    int head = 1, tail = 0;
    Que[++tail] = 1;
    For(i, 2, Cntlen) {
        while(head <= tail && Que[head] + len < i) head++;
        if(head <= tail) Checkmin(Dis[Cnt[i]], Dis[Cnt[Que[head]]] + (i - Que[head]) * d + mod);
        while(head <= tail && Dis[Cnt[i]] - i * d < Dis[Cnt[Que[tail]]] - Que[tail] * d) tail--;
        Que[++tail] = i;
    }
}
inline void DP2(int p, int d, int New) {
    int pos = -1, i = p; Cntlen = 0;
    do {
        if(pos == -1 || f[pos] > f[i]) pos = i;
        i = (i + d) % New;
    }while(i != p);
    i = pos;
    do {
        Cnt[++Cntlen] = i, i = (i + d) % New;
    }while(i != pos);
    int minn = f[Cnt[1]] - d;
    For(i, 2, Cntlen) f[Cnt[i]] = min(f[Cnt[i]], minn + i * d), minn = min(minn, f[Cnt[i]] - i * d);
}
inline void Change(int New) {
    For(i, 0, New - 1) f[i] = INF;
    For(i, 0, mod - 1) Checkmin(f[Dis[i] % New], Dis[i]);
    int g = __gcd(mod, New);
    For(i, 0, g - 1) DP2(i, mod, New);
    For(i, 0, New - 1) Dis[i] = f[i];
}
inline void Work(int d, int len) {
    int g = __gcd(d, mod);
    For(i, 0, g - 1) DP1(i, d, len);
}
inline void Solve() {
    int L = 1; mod = Period[L];
    while(L < m) {
        int R = L + 1;
        while(R < m && Period[R] - Period[R - 1] == Period[R + 1] - Period[R]) R++;
        Work(Period[L + 1] - Period[L], R - L), L = R + 1;
        if(L <= m) Change(Period[L]), mod = Period[L];
    } 
}
inline void Clear() {
    m = Answer = 0;
    For(i, 0, n) Fail[i] = Dis[i] = INF;
}
signed main() {
//    freopen("P4156.in", "r", stdin);
//    freopen("P4156.out", "w", stdout);
    T = read();
    while(T--) {
        n = read(), W = read() - n, Clear();
        scanf("%s", S + 1); KMP(), Dis[0] = 0;
        Solve();
        For(i, 0, mod - 1) 
            if(Dis[i] <= W) Answer += (W - Dis[i]) / mod + 1;
        printf("%lld\n", Answer);
    }
    return 0;
}