#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pos string::npos
#define endl '\n'
#define inf 1e18
typedef unsigned long long ull;
const int mod = 1e9+7;
const int N = 1e6+10;
const int Maxn = 2e5+5;
template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}
int Inv[N],F[N];//组合数C2
int gcd(int a,int b){ return b == 0 ? a : gcd(b,a%b);}
int lcm(int a,int b){return (a/gcd(a,b)*b);}
int km(int a,int b,int mod)
{int ans=1;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;}
int km1(int a,int b,int mod)//指数取模,2^2^i,单求2^i要取模MOD-1
{int ans=1;mod--;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;}
int C(int a,int b,int p){if(b>a) return 0;int res=1;for(int i=b,j=a;i>=1;i--,j--){res=res*j%p;res=res*km(i,p-2,p)%p;}return res;}
int Lucas(int a,int b,int p){if(a<p&&b<p) return C(a,b,p);return C(a%p,b%p,p)*Lucas(a/p,b/p,p)%p;}
int C2(int a,int b,int p){return F[a]*Inv[a-b]%p*Inv[b]%p;}
void C2init(int n,int p){n--;F[0]=F[1]=1;for(int i=2;i<=n;i++)F[i]=F[i-1]*i%p;Inv[n]=km(F[n],p-2,p);for(int i=n-1;i>=0;i--)Inv[i]=Inv[i+1]*(i+1)%p;}
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
struct edge{
    int v,w;
};
struct matrix{
    int c[5][5];
    matrix(){memset(c,0,sizeof c);}
}A,B;
matrix operator*(matrix &x,matrix &y){
    matrix t;
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            for(int k=1;k<=4;k++){
                //t.c[i][j]=(t.c[i][j]+mul(x.c[i][k],y.c[k][j]))%m;
                t.c[i][j]=(t.c[i][j]+(x.c[i][k]*y.c[k][j])%mod)%mod;
            }
        }
    }
    return t;
}
void km2(int k){
    while(k){
        if(k&1) A=A*B;
        B=B*B;
        k>>=1;
    }
}
int n,m,k,q,ss[N];
void solve() 
{
    string x="nanjing";
    vector<pii> ve;
    cin>>n>>k;
    for(int i=0;i<=n;i++) ss[i]=0;
    string s;
    cin>>s;
    for(int i=0;i<n;i++){
        if(s[i]=='n'){
            int j=i,cnt=0;
            while(s[j%n]==x[cnt]){
                j++,cnt++;
            }
            if(cnt==x.size()) {
                j=(j-1)%n;
                //cout<<i<<" "<<j<<endl;
                if(i<j) {
                    ss[0]++,ss[i+1]--;
                    ss[i+8]++;
                }
                else{
                    ss[j+1]++,ss[i+1]--;
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<=min(n,k);i++){
        if(i>=1)ss[i]+=ss[i-1];
        ans=max(ans,ss[i]);
    }
    cout<<ans<<endl;
}
signed main()
{
    ios;
    int T=1;
    //C2init(N,mod);
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}