#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
template<typename T>void tomin(T& x,T y){x = min(x,y);}
template<typename T>void tomax(T& x,T y){x = max(x,y);}
//
int T,n,k,m = 7,f[N],pre[N],suf[N],ans;
string s,t=" nanjing";

void solve(){
    cin>>n>>k; tomin(k,n-1);
    cin>>s; s = " "+s; 
    ans = 0; for(int i=0;i<=n+1;i++)f[i] = pre[i] = suf[i] = 0;
    for(int i=1;i<=n-m+1;i++){
        f[i] = 1;
        for(int j=1;j<=m;j++)f[i] &= s[i+j-1] == t[j];
    }
    for(int i=1;i<=n;i++)pre[i] = pre[i-1] + f[i]; for(int i=n;i>=1;i--)suf[i] = suf[i+1] + f[i];

    for(int i=0;i<=k;i++){
        int cnt = pre[i] + suf[i+1];
        for(int j=1;j<m;j++){
            if(m-j > i || j > n-i)continue;
            int w = 1;
            for(int k=1;k<=j;k++)w &= t[j-k+1] == s[n-k+1];
            for(int k=1;k<=m-j;k++)w &= t[j+k] == s[k];
            cnt += w;
        }
        tomax(ans,cnt);
    }
    cout<<ans<<"\n";
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>T; while(T--)solve();
    return 0;
}