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

void solve()
{
	int n,k;
	cin >>n >>k;
	string s;
	cin >>s;
	if(n<7)
	{
		cout << 0 <<endl;
		return ;
	}
	int ss = s.size();
	k = min(ss,k);
	s = s + s;
	s = " " + s;
	vector <int> sum(n * 2 + 50);
	for(int i = 1; i <= n * 2 - 6; i ++)
	{
		sum[i] = sum[i - 1];
		if(s.substr(i,7) == "nanjing")
		{
			sum[i] ++;
		}
	}
	int maxn = 0;
	for(int i = 1; i <= k + 1; i ++)
	{
		maxn = max(maxn,sum[i + n - 7] - sum[i - 1]);
		//cout <<sum[i + n - 7] << " "
	}
	cout <<maxn <<endl;
}

int main()
{
	int t;
	cin >>t;
	while(t --)
	{
		solve();
	}
	//string s;
	//cin >> s;
}