#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;

int T;
int n,k;
string s;
int sum[maxn*2];

int main(){
	ios::sync_with_stdio(0);
	cin>>T;
	while(T--){
		cin>>n>>k;
		cin>>s;
		k=min(n-1,k);
		for(int i=0;i<k;i++)
			s.push_back(s[i]);
		
		for(int i=6;i<s.size();i++){
			sum[i]=sum[i-1]+(s.substr(i-6,7)=="nanjing");
		}
		int ans=0;
		for(int i=0;i+n-1<s.size();i++)
			ans=max(sum[i+n-1]-(i==0?0:sum[i-1]),ans);
		cout<<ans<<endl;
	}
	
	
	
	return 0;
}