#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
void solve(){
	int n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	s+=s;
	if(n<7){
		cout<<0<<endl;
		return;
	}
	int ans=0;
	for(int i=0;i<min(k+1,7);i++){
		int cnt=0;
		int ed=i+n-1;
		for(int j=i;j+6<=ed;j++){
			if(s.substr(j,7)=="nanjing"){
				cnt++;
			}
		}
		ans=max(ans,cnt);
	}
	cout<<ans<<endl;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}