#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int read()
{
    int a = 0,x = 1;char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') x = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9') {a = a*10 + ch-'0';ch = getchar();}
    return a*x;
}

const int N=1e6+7;
char s[N],s0[] = "nanjing";
int arr[N],n,k;
void solve()
{
    n = read(),k = read();int ans = 0;
    scanf("%s",s+1);
    for(int i = 1+n;i <= n+n;i ++) s[i] = s[i-n],arr[i] = arr[i-n] = 0;
    for(int i = 1;i <= n+n;i ++) {
        ++ arr[i];
        for(int j = 0;j < 7;j ++) {
            if(s[i+j] != s0[j]) {--arr[i];break;}
        }
        arr[i] += arr[i-1];
    }
    for(int i = n-7+1;i <= n+n - 7+1 && i <= n-7+1 + k;i ++) ans = max(ans,arr[i] - arr[i-(n-7+1)]);
    printf("%d\n",ans);
}

int main()
{
    // freopen("in.in","r",stdin);freopen("out.out","w",stdout);
    int T = read();
    while(T --) solve();
}