#include <bits/stdc++.h>

const int N = 2e5 + 5;

int n, k, a[N];
char str[N];

void run() {
    scanf("%d%d", &n, &k);
    scanf("%s", str);
    if (n <= 6) { printf("0\n"); return; }
    for (int i = 0; i < n; i++)
        str[i + n] = str[i];
    for (int i = 0; i < n + n; i++) {
        a[i] = 0;
        if (i + 6 < n + n && str[i] == 'n' && str[i + 1] == 'a' && str[i + 2] == 'n' && str[i + 3] == 'j' && str[i + 4] == 'i' && str[i + 5] == 'n' && str[i + 6] == 'g')
            a[i] = 1;
    }
    a[n + n] = 0;
    for (int i = n + n; i >= 1; i--)
        a[i - 1] += a[i];
    int ans = 0;
    for (int i = 0; i <= std::min(k, n - 1); i++)
        ans = std::max(ans, a[i] - a[i + (n - 5)]);
    printf("%d\n", ans);
}

int main() {
    int T;
    scanf("%d", &T);
    for (; T; T--) run();
    return 0;
}