#include<cstdio>
#include<algorithm>
using namespace std;

int T, n, k;
char s[200005];
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        for (int i = 1;i <= n;i++) {
            scanf(" %c", &s[i]);
        }

        auto check = [&]() -> int {
            int cnt = 0;
            for (int i = 1;i + 6 <= n;i++) {
                if (s[i] == 'n' && s[i + 1] == 'a' && s[i + 2] == 'n' && s[i + 3] == 'j' && s[i + 4] == 'i' && s[i + 5] == 'n' && s[i + 6] == 'g')
                    cnt++;
            }
            return cnt;
            };

        if (k > 7) k = 7;

        int ans = 0;
        ans = max(ans, check());
        for (int i = 1;i <= k;i++) {
            s[0] = s[1];
            for (int j = 1;j < n;j++) s[j] = s[j + 1];
            s[n] = s[0];
            ans = max(ans, check());
        }

        printf("%d\n", ans);
    }
}