#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;
    for ( ; i + 7 - 1 <= n; i++) {
        if (s.substr(i, 7) == "nanjing") {
            break;
        }
    }

    int ans = 0;

    for ( ; i + 6 <= n + min(i - 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());
}