#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=998244353;
char s[400005];
bool check(int i){
	if(s[i]=='n' && s[i+1]=='a' && s[i+2]=='n' && s[i+3]=='j' && s[i+4]=='i' && s[i+5]=='n' && s[i+6]=='g')
		return 1;
	else 
		return 0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
		int n,k;
		cin>>n>>k;
		int kk=k;
		int ccnt=0;
		for(int i=1;i<=n;i++){
			cin>>s[i];
			if(kk){
				s[n+i]=s[i];
				kk--;
				ccnt++;
			}
		}
		int ff=0,cnt=0,f=0;
		for(int i=1;i<=n+ff;i++){
			if(s[i]=='n'){
				if(check(i)){
					if(f==0){
						ff=min(i-1,k);
						f=1;
					}
					cnt++;
				} 
			}
		}
		for(int i=1;i<=n+ccnt;i++){
			s[i]=0;
		}
		cout<<cnt<<endl;
	}
}