#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,T,a[N],cnt[3],k,sum[N];
char s[N],ch[N];
bool ppp(int x){
	for(int i=x-7+1,j=1;i<=x;++j,++i){
		if(s[i]!=ch[j])return 0;
	}
	return 1;
}
signed main(){
//	ios::sync_with_stdio(0);
	ch[1]='n',ch[2]='a',ch[3]='n',ch[4]='j',ch[5]='i',ch[6]='n',ch[7]='g';
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&k);
		scanf("%s",s+1);
		for(int i=1;i<=n+min(7,k);++i){
			sum[i]=0;
		}
		for(int i=1;i<=min(7,k);++i)s[i+n]=s[i];
		for(int i=7;i<=n+min(7,k);++i){
			if(ppp(i)){
				++sum[i];
//				cout<<i<<endl;
			}
		}
		for(int i=1;i<=n+min(7,k);++i){
			sum[i]+=sum[i-1];
		}
//		cout<<sum[n]<<endl;
		int ans=0;
		for(int i=1;i<=min(k,7)+1;++i){
			ans=max(ans,sum[i+n-1]-sum[i+5]);
		}
		printf("%d\n",ans);
	}
}