#include<bits/stdc++.h>
using namespace std;
typedef  long long LL;
typedef pair<int,int> PII;
const int N=2000010,M=2000010;
const int mod=1e9+7;
int INF = 1e9;

PII find(multiset<PII> st){
    map<int,int> mp;


    for(auto [x,y]:st){
        if(mp[x]){
            return {x,y};
        }

        mp[x]=1;
    }
    
    return {-1,-1};
}


void solve(){
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;


    s+=s;

    string t="nanjing";
    int cnt=0;
    for(int i=0;i<n;i++){
        bool sg=true;
        if(i+t.size()-1>=s.size()) break;
        int j,g;
        for(j=0,g=i;j<t.size();j++,g++){
            if(s[g]==t[j]&&j==t.size()-1) break;
            if(s[g]==t[j]) continue;
            sg=false;
            break;
        }
        if(!sg) continue;
        if(g<n) cnt++;
        else if(g-n+1<=k) cnt++;
    }

    cout<<cnt<<endl;
}

    
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
 
    return 0;
}