#include<bits/stdc++.h>
using namespace std;

#define int long long
#define MAXN 1100005

char a[MAXN];
int n,k;
int f[MAXN];
string s = "nanjing";
int ss[MAXN];

signed main() {
    int T;
    cin >> T;
    while(T --) {
        cin >> n >> k;
        for(int i = 0; i <= n*2+20; i ++) {
            a[i] = ss[i] = f[i] = 0;
        }
        if(k > n) k = n;
        scanf("%s",a+1);
        if(n < 7) {
            cout<<0<<"\n";
            continue;
        }
        for(int i = 1; i <= k; i ++)
            a[i+n] = a[i];
        for(int i = 1; i <= n+k; i ++) {
            f[i] = 1;
            for(int j = i; j < i+7; j ++) {
                if(a[j] != s[j-i])
                    f[i] = 0;
            }
            ss[i] = ss[i-1]+f[i];
        }
        int an = 0;

        for(int i = 1; i <= k+1; i ++) {
            an = max(an,ss[i+n-7]-ss[i-1]);
        }
        cout<<an<<"\n";
    }
    return 0;
}
/*
4
21 10
jingicpcnanjingsuanan
21 0
jingicpcnanjingsuanan
21 3
nanjingnanjingnanjing
4 100
icpc
*/