#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

void solve(){
	int N, K;
	cin >> N >> K;
	int ans = 0;
	string p = "nanjing";
	string s;
	cin >> s;
	for(int i = 0; i <= min(8ll, K); i ++){
		int tans = 0;
		for(int j = 0; j <= N - 7; j ++){
			if(s.substr(j, 7) == "nanjing"){
				tans ++;
			}
		}
		s.push_back(s.front());
		s.erase(s.begin());
		ans = max(tans, ans);
	}
	cout << ans << endl;
}

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