#include <bits/stdc++.h>
using namespace std;
int t,n,k;
string S,T="nanjing";
int op[400011],s[400011];
int main()
{
    cin>>t;
    while(t--){
        cin>>n>>k;
        k=min(k,n-1);
        cin>>S;
        for(int i=0;i<k;++i)S+=S[i];
        
        for(int i=0;i<n+k;++i){
            op[i]=0;
        }
        for(int i=0;i+T.size()-1<S.size();++i)
        {
            bool flag=1;
            for(int _=0;_<7;++_)if(S[i+_]!=T[_])
                {
                    flag=0;
                    break;
                }
            op[i]=flag;
        }
        s[0]=0;
        for(int i=0;i<n+k;++i){
            s[i+1]=s[i]+op[i];
        }
        int ans=0;
        for(int i=n;i<=n+k;++i)
        {
            ans=max(ans,s[i]-s[i-n]);
        }
        cout<<ans<<"\n";
    }
}