#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define MAXN 105
ll res[MAXN];
string ok = "nanjing";
int check(string s)
{
	int res = 0;
	for (int i = 0; i + 6 < s.size(); i++) {
		if (s.substr(i, 7) == ok) {
			res++;
			i += 6;
		}
	}
	
	return res;
}
void solve()
{
	ll n, k;
	string s;
	cin >> n >> k >> s;
	
	if (n <= 6) {
		cout << 0 << endl;
		return;
	}
	
	for (int t = 0; t <= min(7ll, n); t++) {
		string ans = "";
		for (int i = t; i < n; i++) {
			ans += s[i];
		}
		for (int i = 0; i < t; i++) {
			ans += s[i];
		}
		
		res[t] = check(ans);
	}
	
	ll anss = 0;
	for (int i = 0; i <= min(k, 8ll); i++) {
		anss = max(anss, res[i]);	
	}
	
	cout << anss << endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
	
	
	return 0;
}