#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
using i64 = long long;

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

    string s;
    cin >> s;

    k = min(k + 1, 7);
    int ans = 0;

    while (k--) {
        int cnt = 0;
        for (int i = 0; i + 6 < s.size(); i++) {
            if (s.substr(i, 7) == "nanjing") {
                cnt++;
            }
        }
        ans = max(ans, cnt);
        s += s.front();
        s.erase(s.begin());
    }

    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}