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

using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n) for(int i=0;i<(n);++i)
#define sizc(x) ((int)(x).size())
#define allc(x) (x).begin(),(x).end()
#define fir first
#define sec second

constexpr int N = 2e5+5;

int n,m;
char s[N*2];
int p[N*2];

void solve(){
    cin>>n>>m;m=min(m,n-1);
    if(n<=6){cout<<"0\n";return;}
    rep(i,1,n)cin>>s[i],s[i+n]=s[i+2*n]=s[i];
    rep(i,1,2*n)p[i]=0;
    string t="nanjing";
    rep(i,1,2*n-6){
        p[i]=1;
        repn(j,7)if(s[i+j]!=t[j])p[i]=0;
        p[i]+=p[i-1];
    }
    int ans=0;
    rep(i,1,m+1)ans=max(ans,p[i+n-7]-p[i-1]);
    cout<<ans<<'\n';;
}

signed main(){
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

    int T;cin>>T;
    while(T--)solve();
}