#include <bits/stdc++.h>
#define For(i, l, r) for (int i=l; i<=r; ++i)
using namespace std;

const char a[] = {'n', 'a', 'n', 'j', 'i', 'n', 'g'};
const int N = 200010;
int T, n, k;
char c[N];
signed main() {
    cin >> T;
    while (T -- > 0) {
        scanf("%d%d", &n, &k);
        scanf("%s", c);
        int now = 0, ans = 0;
        For(i, 0, min(6, k)) {
            int cnt = 0;
            For(j, 0, n-1) {
                if (c[(j+i)%n] == a[now]) {
                    ++ now;
                    if (now == 7) {
                        now = 0; ++ cnt;
                    }
                }
            }
            ans = max(ans, cnt);
        }
        printf("%d\n", ans);
    }
    return 0;
}
/*
4
21 10
jingicpcnanjingsuanan
21 0
jingicpcnanjingsuanan
21 3
nanjingnanjingnanjing
4 100
icpc
*/