#include<bits/stdc++.h>
using namespace std;
using i64=long long;
using u64=unsigned long long;
#define ll long long
const int inf=1e9;
const ll inff=1e18;
using i128=__int128;

void solve(){
    int n,k;
    cin>>n>>k;
    k=min(n,k);
    string s;
    cin>>s;
    if(n<7){
        cout<<0<<'\n';
        return;
    }
    s=s+s;
    int cnt=0;
    int ans=0;
    // "nanjing"
    for(int i=0;i<n-6;i++){
        if(s.substr(i,7)=="nanjing"){
            cnt++;
            i+=6;
        }
    }
    ans=cnt;
    int l=0,r=n-6;
    while(l<(n+k-6) && r<(n+k-6)){
        // cout<<'\n'<<l<<' '<<r<<'\n';
        // cout<<s.substr(r,7)<<'\n';
        if(s.substr(r,7)=="nanjing"){
            cnt++;
        }
        r++;
        if(s.substr(l,7)=="nanjing"){
            cnt--;
        }
        l++;
        ans=max(ans,cnt);
    }
    cout<<ans<<'\n';
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t=1;
    cin>>t; 
    while(t--){
        solve();
    }
    return 0;
}