#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int T, n, k, ans;
char s[N * 2];
int cnt[N];
void solve() {
    scanf("%d%d", &n, &k);
    scanf("%s", s + 1);
    for(int i = n + 1; i <= n * 2; ++i) s[i] = s[i - n];
    for(int i = 1; i <= n * 2; ++i) cnt[i] = 0;
    ans = 0;
    for(int i = 7; i <= n * 2; ++i) {
        cnt[i] += cnt[i - 1];
        if(s[i - 6] == 'n' && s[i - 5] == 'a' && s[i - 4] == 'n' && s[i - 3] == 'j' && s[i - 2] == 'i' && s[i - 1] == 'n' && s[i] == 'g') {
            ++cnt[i];
        }
    }
    for(int i = n; i <= min(n + k, 2 * n); ++i) {
        ans = max(ans, cnt[i] - cnt[i - n - 1]);
    }
    printf("%d\n", ans);
}

signed main() {
    scanf("%d", &T);
    while(T--) solve();
}