#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+10;

char s[maxn<<1];
int sum[maxn<<1];

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,k;
		scanf("%d%d%s",&n,&k,s+1);
		for(int i=1;i<=n;i++) s[i+n]=s[i];
		for(int i=1;i+6<=n*2;i++)
			if(s[i]=='n'&&s[i+1]=='a'&&s[i+2]=='n'&&s[i+3]=='j'&&s[i+4]=='i'&&s[i+5]=='n'&&s[i+6]=='g')
				sum[i]=sum[i-1]+1;
			else
				sum[i]=sum[i-1];
		int ans=0;
		for(int i=0;i<=min(n-1,k);i++)
			ans=max(ans,sum[i+n-6]-sum[i]);
		printf("%d\n",ans);
	}
	return 0;	
}