#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
const int N=2e5+10;
int T,n,k,t[N];
char a[N];
const string s="nanjing";
void work(){
    scanf("%d%d%s",&n,&k,a);
    for(int i=0;i<n;i++){
        [&](){
            t[i]=0;
            for(int j=0;j<s.length();j++){
                if(s[j]!=a[(i+j)%n])return;
            }
            t[i]=1;
        }();
    }
    // debug(ary(t,0,n-1));
    int sum=accumulate(t,t+n,0),ans=0;
    for(int i=0;i<=k&&i<n;i++){
        int cur=sum;
        for(int j=s.length()-1;j>0;j--){
            cur-=t[(i-j+n)%n];
        }
        ans=max(ans,cur);
    }
    printf("%d\n",ans);
}
int main(){
    for(scanf("%d",&T);T--;)work();
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif