#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<numeric>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=2e5+10;
const int N=2e5;
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
int n,k,ans=0;
char s[MAXN];
string str;
int pre[MAXN];
inline void solve(){
	scanf("%d%d",&n,&k);
	scanf("%s",s+1);
	str.resize(n+8);
	for(int i=1;i<=n;i++)
	{
		str[i]=s[i];
	}
	for(int i=n+1;i<=n+7;i++)
	{
		str[i]=s[i-n];
	}
	for(int i=1;i<=n;i++)
	{
		pre[i]=pre[i-1];
		if(str.substr(i,7)=="nanjing"){
			pre[i]++;
		}
	}
	ans=0;
	for(int i=1;i<=k+1&&i<=7;i++)
	{
		ans=max(ans,pre[n-7+i]-pre[i-1]);
	}
	printf("%d\n",ans);
}
signed main(){
	#ifdef LOCAL
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	atexit([](){fprintf(stderr,"%.3lfs\n",(double)clock()/CLOCKS_PER_SEC);});
	#endif
	int t;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
	return 0;
}