#include <bits/stdc++.h>
using namespace std;

using LL = long long;
using ll = long long;

string t = "nanjing";

void solve() {
    int n, k;
    cin >> n >> k;

    k = min(k, n);

    deque<pair<char, bool>> s;
    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        s.emplace_back(c, 0);
    }

    if (n < 7) {
        cout << 0 << "\n";
        return;
    }

    auto check = [&](int i) {
        for (int j = 0; j < 7; j++) {
            if (s[i + j].first != t[j]) return false;
        }
        return true;
    };

    int sum = 0;
    for (int i = 0; i + 7 - 1 < n; i++) {
        bool x = check(i);
        sum += x;
        s[i].second = x;
    }

    int ans = sum;
    for (int i = 0; i < k; i++) {
        sum -= s[0].second;
        s.emplace_back(s[0].first, 0);
        s.pop_front();
        bool x = check(n - 7);
        sum += x;
        s[n - 7].second = x;
        ans = max(ans, sum);
    }

    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

/*
4
21 10
jingicpcnanjingsuanan
21 0
jingicpcnanjingsuanan
21 3
nanjingnanjingnanjing
4 100
icpc
*/