#include <bits/stdc++.h>

using namespace std;

void solve()
{
	int n, k;
	cin >> n >> k;

	string s;
	cin >> s;

	s = s + s;

	int cnt = 0;

	string nanjing = "nanjing";

	//cout << s << endl;

	if(n <= 6) {
		cout << "0\n";
		return;
	}

	int last = n + min(k, 6);

	for(int i = 0; i < last; i ++) {
		//cout << i << ' ';
		if(s[i] == 'n' && i + 6 < last) {
			//cout << i << ' ';
			bool flag = 0;
			string temp = s.substr(i, 7);
			if(temp == nanjing) {
				cnt ++;
				i = i + 6;
			}
		}
	}

	cout << cnt << '\n';
}

int main()
{
	int t;
	cin >> t;

	while(t--)
		solve();

	return 0;
}