#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N=2e5+10;
int n,k;

void solve() {
	string s[10];
	cin>>n>>k>>s[0];
	for(int i=1;i<=min(k,10);i++) {
		s[i]=s[i-1];
		for(int j=0;j<n;j++)
			if(j>0) s[i][j]=s[i-1][j-1];
			else if(j==0) s[i][j]=s[i-1][n-1];
	}
	int ans=0;
	for(int i=0;i<=min(k,10);i++) {
		int nw_ans=0;
		for(int j=6;j<n;j++) {
			bool flg=true;
			flg&=(s[i][j-6]=='n');
			flg&=(s[i][j-5]=='a');
			flg&=(s[i][j-4]=='n');
			flg&=(s[i][j-3]=='j');
			flg&=(s[i][j-2]=='i');
			flg&=(s[i][j-1]=='n');
			flg&=(s[i][j]=='g');
			nw_ans+=flg;
		}
		if(nw_ans>ans) ans=nw_ans;
	}
	cout<<ans<<"\n";
	return ;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int tc;cin>>tc;
	while(tc--) solve();
	return 0;
}