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

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

void solve() {
    cin >> n >> k;
    cin >> txt;
    init();
    if (n < 7) {
        cout << 0 << '\n';
        return;
    }
    txt = " " + txt + txt;
    const string s = "#nanjing";
    int m = 7;
    for (int i = 1; i <= n * 2 - m + 1; i++) {
        bool flag = true;
        for (int j = 1; j <= m; j++) {
            if (txt[i + j - 1] != s[j]) {
                flag = false;
                break;
            }
        }
        if (flag == true) {
            cnt[i]++;
        }
    }
    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;
}