#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>

#define fi first
#define se second
#define mkp std::make_pair
using ll=long long;
using llu=unsigned long long;
using std::max;
using std::min;
template<class T> void cmax(T&a,T b){a=max(a,b);}
template<class T> void cmin(T&a,T b){a=min(a,b);}

namespace xm{
    char sz[200020];
    void _(){
        int N,K;

        scanf("%d%d%s",&N,&K,sz+1);

        int ans=0;
        for(int i=0;i<=min(K,6);++i){
            if(i) sz[N+i]=sz[i];
            int cnt=0;
            for(int j=1;j+6<=N;++j)
                cnt+=(sz[i+j]=='n'
                    &&sz[i+j+1]=='a'
                    &&sz[i+j+2]=='n'
                    &&sz[i+j+3]=='j'
                    &&sz[i+j+4]=='i'
                    &&sz[i+j+5]=='n'
                    &&sz[i+j+6]=='g');
            cmax(ans,cnt);
        }
        printf("%d\n",ans);
    }
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--) xm::_();
    return 0;
}