#include <bits/stdc++.h>
using namespace std;
constexpr int N=200005;
int n,k;
string s;
int a[N*2],sum[N*2];
void solve()
{
    cin>>n>>k;
    cin>>s;
    if(n<7)
    {
        cout<<0<<"\n";
        return;
    }
    k=min(k,n-1);
    string t=s+s;
    for(int i=0;i<n;i++)
        if(t.substr(i,7)=="nanjing") a[i]=1;
        else a[i]=0;
    for(int i=n;i<n*2;i++)
        a[i]=a[i-n];
    for(int i=0;i<n*2;i++)
    {
        sum[i]=a[i];
        if(i>0) sum[i]+=sum[i-1];
    }
    int ans=0;
    for(int i=0;i<=k;i++)
    {
        int cnt=sum[i+n-7];
        if(i>0) cnt-=sum[i-1];
        ans=max(ans,cnt);
    }
    cout<<ans<<"\n";
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}