#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
int n, k;
string s;
int nxt[maxn * 2];

void get_next() {
    for (int i = 2, j = 0; i <= 2 * n; i++) {
        while (j && s[j + 1] != s[i]) {
            j = nxt[j];
        }
        if (s[j + 1] == s[i]) {
            j++;
        }
        nxt[i] = j;
    }
}

int cnt[maxn * 2];
void kmp() {
    int len = 7;
    string s2 = "#nanjing";
    for (int i = 1, j = 0; i <= n * 2; i++) {
        while (j && s2[j + 1] != s[i]) {
            j = nxt[j];
        }
        if (s2[j + 1] == s[i]) {
            j++;
        }
        if (j == len) {
            cnt[i - j + 1]++;
        }
    }
}

int sum[maxn * 2];

void init() {
    for (int i = 0; i <= 2 * n + 3; i++) {
        nxt[i] = 0;
        cnt[i] = 0;
        sum[i] = 0;
    }
}

void solve() {
    cin >> n >> k;
    init();
    cin >> s;
    if (n < 7) {
        cout << 0 << '\n';
        return;
    }
    s = " " + s + s;
    get_next();
    kmp();
    for (int i = 1; i <= n * 2; i++) {
        sum[i] = sum[i - 1] + cnt[i];
    }

    int ans = 0;
    for (int l = 1; l <= min(k + 1, n); l++) {
        int r = l + n - 1;
        ans = max(ans, sum[r - 6] - sum[l - 1]);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}