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

int solve(const string &s) {
    const string s1 = "nanjing";
    int cnt = 0;
    size_t pos = s.find(s1);
    while (pos != string::npos) {
        cnt++;
        pos = s.find(s1, pos + 1);
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        long long n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        int maxn = solve(s);
        string s2 = s + s;
        int minn = min(n, k);
        for (int i = 1; i <= minn; ++i) {
            string current = s2.substr(i, n);
            maxn = max(maxn, solve(current));
        }

        cout << maxn << '\n';
    }

    return 0;
}