#include <bits/stdc++.h>
#define ll long long
#define Ma 1000005
#define mod 1e9+7
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back

using namespace std;

ll n,k;
string s,t="nanjing";

void sol()
{
	cin>>n>>k>>s;
	k=min(k,7ll);
	ll ans=0;
	s+=s;
	for (ll i=0;i<=k&&i<n;i++)
	{
		ll res=0;
		for (ll j=i;j<i+n;j++)
		{
			ll id=0;
			while (j+id<i+n&&id<7&&t[id]==s[j+id])
				id++;
			res+=(id==7);
		}
		ans=max(ans,res);
	}
	printf("%lld\n",ans);
}


int main()
{
	IOS
	ll tt=1;
	cin>>tt;
	while (tt--)
		sol();
	return 0;
}
/*
1
14 1
gnanjingnanjin
*/