#include<bits/stdc++.h>
using namespace std;
const int N=2e5+9;
int n,k,sum[N];
string s;

inline void solve()
{
    cin>>n>>k;
    cin>>s;
    for(int i=1;i<=n;i++) sum[i]=0;
    if(n<7) return cout<<"0\n",void();
    s=s+s;
    s='.'+s;
    int now=0;
    int ans=0;
    for(int i=1;i<=min(n,n-6+k);i++)
    {
        if(s.substr(i,7)=="nanjing") now++;
        if(i>n-6) now-=(s.substr(i-n+6,7)=="nanjing");
        if(i>=n-6) ans=max(ans,now); 
    }
    cout<<ans<<'\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}
/*
4
21 10
jingicpcnanjingsuanan
21 0
jingicpcnanjingsuanan
21 3
nanjingnanjingnanjing
4 100
icpc
*/