#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }
inline double time() {
    return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int q;
    cin >> q;
    while (q--) {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        if (n < 7) {
            cout << "0\n";
            continue;
        }
        s += s;
        vector<int> ok(n + n);
        for (int i = 0; i < n; ++i) {
            if (s.substr(i, 7) == "nanjing") {
                ok[i] = ok[i + n] = 1;
            }
        }
        for (int i = 1; i < ok.size(); ++i) {
            ok[i] += ok[i - 1];
        }
        if (k >= n) k = n - 1;
        int res = 0;
        for (int i = 0; i <= k; ++i) {
            res = max(res, ok[n - 7 + i] - (i ? ok[i - 1] : 0));
        }
        cout << res << "\n";
    }
}