#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
    int n,d;
    cin>>n>>d;
    string s;
    cin>>s;
    vector<char> c(n+10,'.');
    int ans=0;
    for(int i=0; i<=min(10LL,d); i++){
        int idx=0;
        for(int j=0; j<n; j++){
            int l=j-i;
            l+=n;
            l%=n;
            //cout<<l<<" ";
            c[l]=s[idx];
            idx++;
            idx%=n;
        }
        //for(auto j: c) cout<<j;
        //cout<<endl;
        int cnt=0;
        for(int j=0; j<n-4; j++){
            if(c[j]=='n' and c[j+1]=='a' and c[j+2]=='n' and c[j+3]=='j' and c[j+4]=='i' and c[j+5]=='n' and c[j+6]=='g'){
                cnt++;
            }
        }
        ans=max(ans,cnt);
    }
    cout<<ans<<endl;
}
signed main(){
    int t;
    cin>>t;
    while(t--) solve();
}