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

void solve(){
    int n,k;cin>>n>>k;
    k=min(n,k);
    vector<int>pre(2*n+5);
    string s;cin>>s;
    s+=s;
    for(int i=6;i<n+k;i++){
        pre[i]=pre[i-1];
        if(s[i]=='g'&&s[i-1]=='n'&&s[i-2]=='i'&&s[i-3]=='j'&&s[i-4]=='n'&&s[i-5]=='a'&&s[i-6]=='n'){
            pre[i]++;
        }
    }
    int ans=0;
    for(int i=0;i<=k;i++){
        ans=max(ans,pre[i+n-1]-pre[i+5]);
    }
    cout<<ans<<'\n';
}

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