#include <bits/stdc++.h>
#define eb emplace_back
#define N next
using namespace std;
constexpr unsigned MXSZ = 1 << 20;char buf[MXSZ], *p1, *p2;
#ifdef testing
#define gc getchar()
#else
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MXSZ, stdin), p1 == p2)? EOF : *p1++)
#endif
int read(){
    int x = 0;int c = gc;for (; !isdigit(c); c = gc);
    for (; isdigit(c); c = gc)x = (x * 10) + (c ^ 48);return x;
}
long long readll(){
    long long x = 0;int c = gc;for (; !isdigit(c); c = gc);
    for (; isdigit(c); c = gc)x = (x * 10) + (c ^ 48);return x;
}
int n;long long w;constexpr long long inf = 2e18;char s[500010];
vector<int> period(){vector<int> nxt(n + 1), R;nxt[0] = -1;for (int i = 2, j = 0; i <= n; ++i)
    {while (~j && s[j + 1] ^ s[i])j = nxt[j];nxt[i] = ++j;}for (int i = nxt[n]; ~i; i = nxt[i])R.eb(n - i);return R;}
vector<tuple<int, int, int> > toFDC(vector<int> V){vector<tuple<int, int, int> > R;
    for (auto it = V.begin(); it != V.end(); ){auto jt = it;while (N(jt) != V.end() && *N(jt) - *jt == *N(it) - *it)++jt;
        if (it != jt)R.eb(*it, *N(it) - *it, jt - it);else R.eb(*it, 0, 0); it = N(jt);}return R;}
long long f[500010];int Nwmd;void tmn(long long &x, long long y){if (x > y)x = y;}
void ChgMd(int NewMd){
    static long long fnw[500010];copy_n(f, Nwmd, fnw);fill_n(f, NewMd, inf);for (int i = 0; i < Nwmd; ++i)tmn(f[fnw[i] % NewMd], fnw[i]);
    for (int Bgp = 0, Df = __gcd(NewMd, Nwmd); Bgp < Df; ++Bgp){
        vector<int> Ps{Bgp};for (int v = (Bgp + Nwmd) % NewMd; v != Ps.front(); Ps.eb(v), v = (v + Nwmd) % NewMd);
        rotate(Ps.begin(), min_element(Ps.begin(), Ps.end(), [&](int a, int b){return f[a] < f[b];}), Ps.end());
        long long mn = inf, i = 0;for (int p : Ps)tmn(f[p], mn + i * Nwmd), tmn(mn, f[p] - i++ * Nwmd);
    }
    Nwmd = NewMd;
}
void Jsf(int F, int D, int C){
    for (int Bgp = 0, Df = __gcd(F, D); Bgp < Df; ++Bgp){
        vector<int> Ps{Bgp};for (int v = (Bgp + D) % F; v != Ps.front(); Ps.eb(v), v = (v + D) % F);
        rotate(Ps.begin(), min_element(Ps.begin(), Ps.end(), [&](int a, int b){return f[a] < f[b];}), Ps.end());
        static int Q[500010]; static long long w[500010];
        for (int i = 0, HD = 1, TL = 0, _ = Ps.size(); i < _; ++i){
            if (HD <= TL && Q[HD] < i - C)++HD;
            if (HD <= TL)tmn(f[Ps[i]], w[HD] + 1ll * i * D + F);
            while (HD <= TL && w[TL] > f[Ps[i]] - 1ll * i * D)--TL;
            Q[++TL] = i, w[TL] = f[Ps[i]] - 1ll * i * D;
        }
    }
}
long long Prsh, Prrs;
long long Gths(){
    long long ret = 0;
    for (int i = 1; i <= n; ++i)ret *= 13331, ret += s[i], ret %= 998244353;
    return ret;
}
void work(){
    n = read(), w = readll();int c = gc;while (isspace(c))c = gc;for (int i = 1; i <= n; ++i)s[i] = c, c = gc;
    long long Nhs = Gths();if (Nhs == Prsh){cout << Prrs << endl;return;}Prsh = Nhs;
    w -= n;Nwmd = n;auto Ls = toFDC(period());fill_n(f, n, inf);f[0] = 0;for (auto [F, D, C] : Ls){ChgMd(F);Jsf(F, D, C);}
    long long res = 0;for (int i = 0; i < Nwmd; ++i)if (f[i] <= w)res += (w - f[i]) / Nwmd + 1;cout << res << endl;Prrs = res;
}
signed main(){int t = read();while (t--)work();return 0;}
//refer https://www.luogu.com.cn/article/6h0eem0a