#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(x) for(ll i = 1; i <= x; i ++)

void solve(){
    ll n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    s = s + s;
    ll ans1 = 0;
//    cerr << s << endl;
    if(n < 7) { cout << 0 << endl;return ; }
    vector<ll> pre(2 * n + 1);

    for(int i = 0; i < n - 7 + 1 ; i ++){
        if(s.substr(i, 7) == "nanjing"){
            pre[i + 1] ++;
            i += 6;
        }
    }

    for(int i = n - 6; i < 2 * n - 6; i ++){
        if(s.substr(i, 7) == "nanjing"){
            pre[i + 1] ++;
            i += 6;
        }
    }

    f(2 * n){
        pre[i] += pre[i - 1];
//        cout << i << ':' << pre[i] << endl;
    }
    ll ans = 0;
    f(min(n, k + 1)){
        ans = max(ans, pre[i + n - 1 - 6] - pre[i - 1]);
    }
    cout << ans << endl;
}
int main (){
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

//nanjingnanjing

//4 1  15 -> n 2