#include<bits/stdc++.h>
using namespace std;
int t;

int n,k;

int main(){
    cin>>t;
    while(t--){
        cin>>n>>k;
        string s,st; 
        cin>>s;
        st=s;
        s=s+st;
        int ma=0;
        for(int j=0;j<=k&&j<=7;j++){
            int cnt=0;
            for(int i=j;i+6<s.size()/2+j;i++){
                if(s.substr(i,7)=="nanjing") cnt++; 
            }
            ma=max(ma,cnt);
        }
        cout<<ma<<endl;
    }
}