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

void QAQ() {
    int n, m;
    cin >> n >> m;

    string s;
    cin >> s;
    s = s + s;
    s = " " + s;
    int i = 1, fl = 0;
    for ( ; i + 6 <= n; i++) {
        if (s.substr(i, 7) == "nanjing") {
            fl = 1;
            break;
        }
    }

    if (fl == 0) {
        int ans = 0;
        for (int j = i; j <= n; j++) {
            int res = 0;
            for (int ti = j; ti + 6 <= n + min(j - 1, m); ti++) {
                if (s.substr(ti, 7) == "nanjing") {
                    res++;
                    ti += 6;
                }
            }
            ans = max(ans, res);
        }
        cout << ans << "\n";
        return;
    }

    int ans = 0;
    int t = i;

    for ( ; i + 6 <= n + min(t - 1, m); i++) {
        if (s.substr(i, 7) == "nanjing") {
            ans++;
            i += 6;
        }
    }

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

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int t = 1;
    cin >> t;
    for (cout << fixed << setprecision(12); t--; QAQ());
}