#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
char s[400005];
int sum[400005];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int t;cin>>t;
    while(t--){
        int n,k;cin>>n>>k>>s,k=min(k,n-1);
        for(int i=0;i<n;i++) s[i+n]=s[i];
        for(int i=0;i<n+n;i++) sum[i]=0;
        for(int i=6;i<n+n;i++) if(s[i-6]=='n'&&s[i-5]=='a'&&s[i-4]=='n'&&s[i-3]=='j'&&s[i-2]=='i'&&s[i-1]=='n'&&s[i]=='g'){
            sum[max(i-n+1,0)]++,sum[i-5]--;
        }
        for(int i=1;i<n+n;i++) sum[i]+=sum[i-1];
        int ans=0;
        for(int i=0;i<=k;i++) ans=max(ans,sum[i]);
        cout<<ans<<endl;
    }
}