#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
    int n,k;
    cin>>n>>k;
    string s;
    cin >> s;
    if(s.size()<7){
        cout<<0<<'\n';
        return;
    }
    string tmp = s.substr(s.size()-6);
    int ans=0;
    for(int i=0;i+6<(int)s.size();i++){
        int r=i;
        string k=s.substr(i,7);
        if(k=="nanjing"){
            ans++;
            i=i+6;
        }
    }
    int res=0;
    string w="nanjing";
    for(int i=s.size()-6;i<(int)s.size();i++){
        string tmp=s.substr(i);
        string tmp1=w.substr(0,s.size()-i);
        if(tmp==tmp1){
            res=max(res,(int)s.size()-i);
        }
    }
    for(int i=0;i<min(k,6ll);i++){
        string tmp=s.substr(0,i);
        string tmp1=w.substr(w.size()-i);
        if(tmp==tmp1&&res>=6-i){
            ans++;
            break;
        }
    }
    cout<<ans<<'\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}