#include<bits/stdc++.h>
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_back

using namespace std;

inline ll read()
{
	ll f=1,sum=0;char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-1;c=getchar();}
	while (isdigit(c)) {sum=sum*10+c-'0';c=getchar();}
	return sum*f;
}
const int MAXN=200100;
char s[MAXN];
const char str[]="nanjing";
int main()
{
	int T=read();
	while (T--)
	{
		int n=read(),k=read();
		scanf("%s",s+1);
		for (int i=1;i<=min(7,k);i++) s[i+n]=s[i];
		int ans=0;
		for (int i=0;i<=min(7,k);i++)
		{
			int st=i,ed=i+n-1,now=0;
			for (int j=st;j<=ed;j++)
			{
				bool flag=true;
				for (int k=0;k<7;k++) flag&=(str[k]==s[j+k]);
				if (flag) now++;
			}
			ans=max(ans,now);
		}
		cout<<ans<<'\n';
	}
	return 0;
}