#include <iostream> 
#include <vector> 
using namespace std;
void slove() {
	int n, k;
	cin >> n >> k;
	k = min(n, k);
	string str;
	cin >> str;
	if (str.size() >= 7)
	{
		for (int i = 0; i < 6; i++)
		{
			str.push_back(str[i]);
		}
	}
	vector<int> in(str.size(), 0);
	int cnt = 0;
	for (int i = 0; i + 6 < str.size(); i++)
	{
		if (str.substr(i, 7) == "nanjing")
		{
			cnt++; for (int j = 1; j < 6; j++) in[i + j] = 1;
		}
	}
	if (str.size() >= 7)
	{
		for (int i = 0; i < 6; i++)
		{
			in[i] = in[str.size() - 6 + i];
		}
	}
	for (int i = 0; i <= k; i++)
	{
		if (!in[i])
		{
			cout << cnt << "\n"; return;
		}
	}
	cout << (cnt - 1) << "\n";
	return;
}
int main()
{
	// freopen("in.txt" , "r" , stdin); 
	int cnt = 1; 
	cin >> cnt;
	while (cnt--) 
	{ 
		slove(); 
	}
}