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

void solve() {
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	s = " " + s + s;
	vector<int>v1(n * 2 + 1), v2(n * 2 + 1);
	for (int i = 1; i <= n * 2; i++) {
		if (i + 6 <= n * 2 && s.substr(i, 7) == "nanjing")
			v1[i] = 1;
		if (i - 6 >= 1 && s.substr(i - 6, 7) == "nanjing")
			v2[i] = 1;
	}
	int c = 0;
	for (int i = 1; i <= n; i++) {
		if (v2[i])
			c++;
	}
	int ans = c;
	for (int i = n + 1; i <= min(n + k, 2 * n); i++) {
		if (v1[i - n])
			c--;
		if (v2[i])
			c++;
		ans = max(ans, c);
	}
	cout << ans << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}