#include<bits/stdc++.h>
using namespace std;
int cnt[400010];
int nx[8]={-1,0,0,1,0,0,1,0};
int main() {
	ios::sync_with_stdio(false);
	int T;
	cin>>T;
	string t="nanjing";
	while(T--) {
		int n,k;
		cin>>n>>k;
		string s;
		cin>>s;
		s=s+s;
		int j=0;
		int i=1;
		while(i<=n*2) {
			if(s[i-1]==t[j]) {
				j++;
				if(j==7) {
					cnt[i]=cnt[i-1]+1;
					j=0;
				} 
				else cnt[i]=cnt[i-1];
				i++;
			} 
			else if(j!=0) j=nx[j];
			else {
				cnt[i]=cnt[i-1];
				i++;
			}
		}
		int mx=0;
		for(int l=0; l<=min(k,n-1); l++) {
			mx=max(mx,cnt[l+n]-cnt[l]);
		}
		cout<<mx<<endl;
	}
}