#include<bits/stdc++.h>
using namespace std;
#define int long long
string s;
int cal(int l,int r){
	if(l<1||r>(int)s.size()-1)return 0;
	if(s.substr(l,7)=="nanjing")return 1;
	return 0;
}
void solve(){
	int n,k;cin>>n>>k;
	cin>>s;
	s=" "+s; 
	int sum=0,ans=0;
	for(int i=1;i<=n;i++){
		if(cal(i,i+6))sum++;
	//	cout<<" i:"<<i<<" sum:"<<sum<<"\n";
	}
	ans=sum;
	for(int i=1;i<=min(n,k);i++){
		if(cal(i,i+6))sum--;
		s.push_back(s[i]);
		if(cal((int)s.size()-7,(int)s.size()-1))sum++;
		ans=max(ans,sum);
	}
	cout<<ans<<'\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t=1;
	cin>>t;
	while(t--){
		solve();
	}
}