#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int tt;
	cin>>tt;
	while(tt--){
		int n,k;
		cin>>n>>k;
		string s;
		cin>>s;
		string ss=s+s;
		int cnt=0;
		string tg="nanjing";
		int index=0;
		while(ss.find(tg,index)!=string::npos){
			cnt++;
			index=ss.find(tg,index)+1;
		}
		if(cnt%2==0){
			cout<<cnt/2<<'\n';
			continue;
		}
		else{
			int pos;
			for(int i=0;i<n;i++){
				if(s[i]=='g'){
					pos=i+1;
					break;
				}
			}
			if(pos<=k)cnt=cnt/2+1;
			else cnt=cnt/2;
			cout<<cnt<<'\n';
		}
	}
}