#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N=2e5+10;
int n,k;
string s;

int chk(int delta) {
	int ans=0;
	for(int i=0;i<n;i++) {
		if(i+6+delta>=n+delta) break;
		string nw=""; nw+=s[(i+delta)%n];
		nw+=s[(i+1+delta)%n]; nw+=s[(i+2+delta)%n]; nw+=s[(i+3+delta)%n];
		nw+=s[(i+4+delta)%n]; nw+=s[(i+5+delta)%n]; nw+=s[(i+6+delta)%n];
		if(nw=="nanjing") ans++;
	}
	return ans;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int tc;
	cin>>tc;
	while(tc--) {
		cin>>n>>k>>s;
		int ans=0;
		for(int i=0;i<=min(k,7);i++)
			ans=max(ans,chk(i));
		cout<<ans<<"\n";
	}
	return 0;
}