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

const int N=200050;
char s[N];
int pref[N];
string nanjing="nanjing";

int main(){
    int t;
    scanf("%i",&t);
    while(t--){
        int n,k;
        scanf("%i %i",&n,&k);
        scanf("%s",s);
        if(n<nanjing.size()){
            printf("0\n");
            continue;
        }
        for(int i=0;i<n;i++){
            bool ok=true;
            for(int j=0;j<nanjing.size();j++){
                if(s[(i+j)%n]!=nanjing[j])ok=false;
            }
            pref[i+1]=pref[i];
            if(ok)pref[i+1]++;
        }
        int ans=0;
        int sz=n-nanjing.size()+1;
        for(int i=0;i<min(k+1,n);i++){
            int sum;
            if(i+sz<=n){
                sum=pref[i+sz]-pref[i];
            }else{
                sum=pref[n]-pref[i]+pref[i+sz-n];
            }
            ans=max(ans,sum);
        }
        printf("%i\n",ans);
    }
    return 0;
}