#include <bits/stdc++.h>
#define int long long
using namespace std;
int T;
int n,k;
int32_t main(){
	cin.tie(nullptr)->ios::sync_with_stdio(false);
	cin>>T;
	while(T--){
		cin>>n>>k;
		string s;
		cin>>s;
		if(s.size()<7){
			cout<<0<<endl;
			continue;
		} 
		int sum=0;
		for(int i=0;i<s.size()-6;i++){
			if(s.substr(i,7)=="nanjing"){
				sum++;
			}
		}//循环扫一遍字符串
 		//打表处理边上的串（注意判断左移次数是否够） 
		if(s[0]=='g'&&s.substr(s.size()-6,6)=="nanjin"&&k>=1){
			sum++;
		}
		if(s.substr(0,2)=="ng"&&s.substr(s.size()-5,5)=="nanji"&&k>=2){
			sum++;
		}
		if(s.substr(0,3)=="ing"&&s.substr(s.size()-4,4)=="nanj"&&k>=3){
			sum++;
		}
		if(s.substr(0,4)=="jing"&&s.substr(s.size()-3,3)=="nan"&&k>=4){
			sum++;
		}
		if(s.substr(0,5)=="njing"&&s.substr(s.size()-2,2)=="na"&&k>=5){
			sum++;
		}	
		if(s.substr(0,6)=="anjing"&&s[s.size()-1]=='n'&&k>=6){
			sum++;
		}
		cout<<sum<<endl;//输出答案								
	}
	return 0;
}