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

int n,k;
string s;

string st="nanjing";

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

    cin>>s;

    k=min(k,n);

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

    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 sum=0;
    for(int i=0;i<n;i++)sum+=p[i];

    int ans=sum;

    for(int i=n;i<m;i++){
        sum-=p[i-n];
        sum+=p[i];
        ans=max(ans,sum);
    }

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

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

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

    return 0;
}