#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 2e5 + 10;

char s[MAX];

void solve(){
	int n = read(), k = read();
	for(int i = 1; i <= n; i++)	cin >> s[i];
	int ans = 0;
	for(int i = 1; i <= n - 6; i++){
		if(s[i] == 'n' and s[i + 1] == 'a' and s[i + 2] == 'n' and s[i + 3] == 'j' and s[i + 4] == 'i' and s[i + 5] == 'n' and s[i + 6] == 'g'){
			ans++;
		}
	}
	for(int j = 1; j <= min(k, 7ll); j++){
		for(int i = 1; i < n; i++){
			swap(s[i], s[i + 1]);
		}
		int cnt = 0;
		for(int i = 1; i <= n - 6; i++){
			if(s[i] == 'n' and s[i + 1] == 'a' and s[i + 2] == 'n' and s[i + 3] == 'j' and s[i + 4] == 'i' and s[i + 5] == 'n' and s[i + 6] == 'g'){
				cnt++;
			}
		}
		ans = max(ans, cnt);
	}
	write(ans), endl;
}

signed main(){
	int t = read();
	while(t--)	solve();
	return 0;
}