#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include "lib.h"
#endif
#define rep(i, min, max) for(int i = (min); i <= (max); ++i)
#define nrep(i, max, min) for(int i = (max); i >= (min); --i)
#define reads(str) (scanf("%s", str + 1), strlen(str + 1))
#define case() int Ts = read(); rep(T, 1, Ts)
#define putf(flag) puts((flag) ? "Yes" : "No")
#define put(x) printf("%d ", x)
#define putl(x) printf("%lld ", x)
#define endl() putchar('\n')
using namespace std;

typedef long long ll;
inline int read()
{
    int now=0; bool nev=false; char c=getchar();
    while(c<'0' || c>'9') { if(c=='-') nev=true; c=getchar(); }
    while(c>='0' && c<='9') { now=(now<<1)+(now<<3)+(c&15); c=getchar(); }
    return nev?-now:now;
}

const int N = 1e6 + 10;

char s[N];
char t[] = "nanjing";
int a[N];

bool check(int i) {
    rep(j, 0, 6) if(s[i + j] != t[j]) return 0;
    return 1;
}

int main() {
    case() {
        int n = read(), k = read();
        k = min(n, k);
        reads(s);
        rep(i, 1, n) s[i + n] = s[i];
        rep(i, 1, n * 2) a[i] = a[i - 1] + check(i);
        int maxn = 0;
        rep(i, 1, k + 1) if(i + n - 7 >= 0) maxn = max(maxn, a[i + n - 7] - a[i - 1]);
        put(maxn), endl();
        rep(i, 1, n * 2 + 1) a[i] = 0, s[i] = 0;
    }
}