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

void solve(){
    int n,k;cin>>n>>k;
    string s,ss;cin>>s;
    string ns;
    if(n<7){
        cout<<0<<'\n';
        return;
    }
    ss=s+s;
    int tp=min(n-1,k);
    for(int i=0,j=6;i<=min(k,n-1);i++,j++){
        if(ss.substr(i,j-i+1)=="nanjing"){
            tp=i;
            break;
        }
    }

    ns=s.substr(tp,n-1-tp+1)+s.substr(0,tp);
    //cerr<<ns<<'\n';
    int res=0;
    for(int i=0,j=6;j<=n-1;i++,j++){
        if(ns.substr(i,j-i+1)=="nanjing") res++;
    }
    cout<<res<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--){solve();}
    return 0;
}