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

int n, k;
string s;

void solve() {
    cin >> n >> k;
    cin >> s;
    s = s + s;
    s = " " + s;
    queue<int> q;
    int ans = 0;
    k = min(k, n - 1);
    for (int i = 1; i + 6 <= n + k; ++i) {
        while (q.size() && q.front() < i + 7 - n) q.pop();
        if (s.substr(i, 7) == "nanjing") {
            q.push(i);
        }
        ans = max(ans, (int) q.size());
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
}