#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
int T,n,x,k;
int bb[N];
char s[N],ss[N],t[N];
int ppp(int x){
	for(int i=1;i<=7;++i)
	if(t[i]!=s[x+i-1])return 0;
	return 1;
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>T;
	t[1]='n';
	t[2]='a';
	t[3]='n';
	t[4]='j';
	t[5]='i';
	t[6]='n';
	t[7]='g';
	while(T--){
		cin>>n>>k>>ss;
		if(n<=6){
			cout<<0<<'\n';
			continue;
		}
		k=min(n,k);
		for(int i=1;i<=n;++i)s[i]=ss[i-1];
		for(int i=1;i<=k;++i)s[i+n]=ss[i-1];
		int ans=0;
		for(int i=1;i<=n+k-6;++i)bb[i]=ppp(i),bb[i]+=bb[i-1];
		for(int i=n;i<=n+k;++i)
			ans=max(ans,bb[i-6]-bb[i-n]);
		cout<<ans<<'\n';
	}
}