#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std; 
typedef long long i64; 
const int N = 5e5 + 5; 

int n, nxt[N]; 
char s[N]; 
i64 m, ans, a[N], d[N]; 

void solve(void) {
    cin >> n >> m >> s + 1; 
    for (int i = 2, p = 0; i <= n; ++i) {
        while (p && s[i] != s[p + 1]) p = nxt[p]; 
        if (s[i] == s[p + 1]) ++p; 
        nxt[i] = p; 
    }
    
    int cur = n, tot = 0;
    while (cur) {
        cur = nxt[cur]; 
        a[++tot] = n - cur;
    }

    vector<tuple<int, int, int>> vec; 

    for (int i = 1, j = 1; i <= tot; ++i) {
        j = i; 
        while (j < tot && a[i + 1] - a[i] == a[j + 1] - a[j]) ++j; 
        if (i == j) vec.emplace_back(a[i], a[i], 0); 
        else vec.emplace_back(a[i], a[j], (a[j] - a[i]) / (j - i)), i = j; 
    }
    
    int cec = a[1]; memset(d, 0x3f, sizeof d); 

    __gnu_pbds::priority_queue<pair<i64, int>, greater<pair<i64, int>>> Q; 
    Q.push({0, d[0] = 0}); 
    vector<bool> vis(cec); 

    while (!Q.empty()) {
        auto [w, u] = Q.top(); Q.pop(); 
        if (vis[u]) continue; vis[u] = 1; 
        for (auto [l, r, k] : vec)
            for (int i = l, t = k; i <= r; i += k, t += k) {
                i64 v = (u + i) % cec, tmp = w + i; 
                if (d[v] > tmp) d[v] = tmp, Q.push({d[v], v}); 
                if (d[(u + t) % cec] <= w + t) break; 
            }
    }
    
    i64 ans = 0;
    for (int i = 0; i < cec; ++i)
        if (d[i] <= m - n) ans += (m - n - d[i]) / cec + 1; 
    cout << ans << "\n"; 
}

int main(void) {
    ios::sync_with_stdio(0); 
    int T; cin >> T; 
    while (T--) solve();
    return 0;
}