#include<bits/stdc++.h>
using namespace std;
int t;
int n,m;
char ch[200005];
string nj="nanjing";
int check(int x){
	for(int i=x,j=0;j<7;i=i%n+1,j++){
		if(ch[i]!=nj[j]) return 0;
	}
	return 1;
}
main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		scanf("%s",ch+1);
		if(n<7){puts("0");continue;}
		int sum=0,ans=0;
		for(int i=1;i<=n;i++) sum+=check(i);
		for(int i=1;i<=1+m&&i<=n;i++){
			int psum=sum;
			for(int j=(i+n-7)%n+1;j!=i;j=j%n+1) psum-=check(j);
			ans=max(ans,psum);
		}
		printf("%d\n",ans);
	}
}