#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e6+9;
char t[]="nanjing",s[N];
int n,K;
int a[N];
void work()
{
	scanf("%d%d",&n,&K);
	scanf("%s",s+1);
	if(n<7) return puts("0"),void();
	for(int i=1;i<=n;i++) s[i+n]=s[i];
	for(int i=0;i<=n*2;i++) a[i]=0;
	for(int i=1;i+6<=n*2;i++)
	{
		bool pd=1;
		for(int j=0;j<7;j++)
		if(s[i+j]!=t[j])
		{
			pd=0;
			break;
		}
		if(pd) a[i]=1;
	}
	for(int i=1;i<=n*2;i++) a[i]+=a[i-1];
	int ans=0;
	for(int i=1;i<=K+1&&i<=n;i++) ans=max(ans,a[i+n-7]-a[i-1]);
	printf("%d\n",ans);
}
signed main()
{
	int T;
	scanf("%d",&T);
	while(T--) work();
}