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

#define db(args...){\
    string _s = #args; replace(_s.begin(), _s.end(), ',', ' ');\
    stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); cout << '\n';}
void err(istream_iterator<string> it){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a << ' ';
    err(++it, args...);
}

void solve() {
    int n, k;
    cin >> n >> k;
    k = min(n, k);
    
    string s;
    cin >> s;
    s = ' ' + s + s;

    if (n < 7) {
        cout << "0\n";
        return;
    }
    string t = "nanjing";

    vector<int> a(s.size());
    
    for (int i = 7; i < s.size(); i++) {
        int j = i - 7 + 1;
        string S(s.begin() + j, s.begin() + i + 1);
        a[i] = S == t;
        a[i] += a[i - 1];
    }

    int res = 0;
    for (int i = 1; i <= k + 1 && i <= n; i++) {
        if (i + 7 - 2 < a.size()) res = max(res, a[i + n - 1] - a[i + 7 - 2]);
    }
    cout << res << '\n';
}

// L
// void pre(int n) {
//     vector<int> p(n);
//     iota(p.begin(), p.end(), 0);
//     db(n);
//     do {
//         set<int> st;
//         for (int i = 0; i < n; i++) {
//             st.insert(p[i] ^ i);
//         }
//         if (st.size() == n) {
//             for (auto x : p) cout << x << ' ';
//             cout << '\n';
//             return;
//         } 
//     } while (next_permutation(p.begin(), p.end())); 
//     cout << "No\n";
// }

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

/*
g++ 1.cpp -std=c++20 -o 1 && ./1 < in.txt > out.txt
 */