#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-6) {
                bool flag = true;
                For(ii, 0, 6) {
                    if (c[(j+i+ii) % n] != a[ii]) {
                        flag = false; break;
                    }
                }
                if (flag) ++ cnt;
            }
            ans = max(ans, cnt);
        }
        printf("%d\n", ans);
    }
    return 0;
}
/*
4
21 10
jingicpcnanjingsuanan
21 0
jingicpcnanjingsuanan
21 3
nanjingnanjingnanjing
4 100
icpc
*/