#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2.1e5;
inline LL read(){
	LL x=0,ff=1;
	char c=getchar();
	while(!isdigit(c)&&c!='-') c=getchar();
	if(c=='-') c=getchar(),ff=-1;
	while(isdigit(c)) x=x*10ll+c-'0',c=getchar();
	return x*ff;
}
int n,m;
char c[N],s[7];
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int casecnt=read();
	s[0]='n',s[1]='a',s[2]='n',s[3]='j',s[4]='i',s[5]='n',s[6]='g';
	while(casecnt--){
		n=read(),m=read(); 
		m=min(m,7);
		scanf("%s",c);
		int cnt[3]={0,0,0},ans=0;
		for(int d=0;d<=m;++d){
			int res=0;
			for(int i=0;i<n-6;++i){
				int j=0;
				for(;j<7;++j)
					if(s[j]!=c[(d+i+j)%n])
						break;
//				if(j==7)
//					cerr<<i<<endl;
				res+=j==7;
			}
			ans=max(ans,res);
		}
		printf("%d\n",ans);
	} 
	return 0;
}