#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i=0;i<(n);i++)

void solve(){

    ll N,K;
    cin >> N >> K;
    string S;
    cin >> S;

    if(N<7){
        cout << 0 << endl;
        return;
    }

    vector<ll> nanjing(N,0);
    REP(i,N){
        bool c = true;
        REP(j,7){
            if(S[(i+j)%N]!="nanjing"[j])c=false;
        }

        if(c){
            REP(j,6){
                nanjing[(i+j+1)%N] = 1;
            }
        }
    }

    // REP(i,N){cout << nanjing[i] << " ";}cout << endl;

    ll start = 0;
    REP(i,min(N,K+1)){
        if(nanjing[i]==0){
            start = i;
            break;
        }
    }

    ll Ans = 0;
    REP(i,N-6){
        
        bool c = true;
        REP(j,7){
            if(S[(i+start+j)%N]!="nanjing"[j])c=false;
        }

        if(c)Ans++;
    }

    cout << Ans << endl;

}

signed main(void){
    //cin.tie(nullptr);
    //ios::sync_with_stdio(false);

    ll T;
    cin >> T;
    REP(i,T){solve();}
    
    return 0;
    
}