#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+20;
string s="nanjing";
int n,m;
char str[maxn];
int he[maxn];
bool check(int i)
{
	for(int j=0;j<=6;j++)
	{
		if(s[j]!=str[i-6+j])return false;
	}
	return true;
}
void solve()
{
	cin>>n>>m;
	cin>>str;
	if(n<7)
	{
		cout<<"0\n";
		return;
	}
	for(int i=0;i<8;i++)
	{
		str[i+n]=str[i];
	}
	int cnt=0,mx=0;
	for(int i=0;i<n+min(m,8);i++)
	{
		if(check(i))cnt++;
		if(i>=n&&check(i-n+6))cnt--;
		mx=max(mx,cnt);
	}
	cout<<mx<<"\n";
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}