//
// Created by 16429 on 2024/11/17.
//
#include "bits/stdc++.h"
using namespace std;


int ck(string a,string b){
    if(a.length()!=b.length())return false;

    for(int i = 0 ; i < a.length();++i){
        if(a[i]!=b[i])return false;
    }
    return 1;
}

void work(){
    int n,k;cin>>n>>k;
    string st;cin>>st;
    string t;t = st;
    for(int len = 1,i=0 ; len <= 6;len++,i=(i+1)%n){
        t+=st[i];
    }
    string moshi = "nanjing";
    int ans = 0;
    int tt=0;
    for(int i = 0; i < n ;++i){
        string tem;
        for(int j = 0; j <7 ; ++j){
            tem+=t[i+j];
        }
        if(ck(tem,moshi)){
            ans++;
            if(i+7>n)tt = (i+7)%n;
        }
    }

    if(k<tt){
        ans--;
    }

    cout<<ans<<'\n';

}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while (t--){
        work();
    }
    return 0;
}