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

int n,k;
string s;

string st="nanjing";

inline void solve(){
    cin>>n>>k;

    cin>>s;

    if(n<7)return cout<<"0\n",void();

    k=min(k,n);

    for(int i=0;i<k;i++)s+=s[i];

    // cout<<s<<"\n";

    int m=s.size();

    vector<int>p(m);
    for(int i=0;i+6<m;i++){
        if(s[i]=='n'){
            int flag=1;
            for(int t=0,j=i;t<7;t++,j++){
                if(s[j]!=st[t]){
                    flag=0;
                    break;
                }
            }        
            p[i]=flag;
        }
    }

    int ans=0;

    for(int i=1;i<m;i++)p[i]+=p[i-1];

    for(int i=n-7,t=0;i+6<m;i++,t++)ans=max(ans,p[i]-(t==0?0:p[t-1]));

    cout<<ans<<"\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t=1;
    cin>>t;
    while(t--)solve();

    return 0;
}