#include<bits/stdc++.h>
using namespace std;
/*
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
*/
// #define int long long
#define ld long double
//#define INT __int128
#define eb(x) emplace_back(x)
#define fi first
#define se second
#define sc(x) scanf("%d",&x)
#define SC(x) scanf("%lld",&x)
#define reserve reserve
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<long long, long long> PLL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const ld eps = 1e-12;
const int N = 5e5 + 10, M = N + 10;
int n,k;
char s[N];

void solve(){
    cin>>n>>k;
    scanf("%s",s);
    for(int i=0;i<n;i++){
        s[i+n]=s[i];
    }
    if(n<7){
        puts("0");
        return;
    }
    // printf("%s\n", s);
    int ans=0,mx=0;
    int l=0;
    for(int r=0;r<2*n;r++){ 
        if(r-l+1>n){
            if(s[l]=='n'&&s[l+1]=='a'&&s[l+2]=='n'&&s[l+3]=='j'&&s[l+4]=='i'&&s[l+5]=='n'&&s[l+6]=='g'){
                mx--;
            }
            l++;
        }
        // cout<<"+++ ===== =  "<<l<<" "<<r<<endl;
        if(l>k){
            // cout<<"_______"<<endl;
            break;
        }   
        if(r-l+1>=7){
            if(s[r]=='g'&&s[r-1]=='n'&&s[r-2]=='i'&&s[r-3]=='j'&&s[r-4]=='n'&&s[r-5]=='a'&&s[r-6]=='n'){
                mx++;
            }
        }
        ans=max(ans,mx);
    }
    cout<<ans<<endl;
}

signed main(){
    // ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T=1,cas=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}