#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <ctime>
#include <cstdio>
#include <random>
#include <vector>
#include <bitset>
#include <cassert>
#include <cstring>
#include <algorithm>
#define fi first
#define se second
#define MISAKA main
#define ll long long
#define eb emplace_back
#define pii pair<int,int>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define _rep(i,a,b) for(int i=a;i>=b;--i)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define FIO(FILE) freopen(FILE".in","r",stdin),freopen(FILE".out","w",stdout)
using namespace std;
inline int read(){
    char ch=getchar();int f=1,x=0;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
const int N=4e5+10,mod=998244353;
int n,k,pre[N],suf[N];char s[N];
bool ck(int x){
    string t;
    rep(i,x,x+6) t+=s[i];
    return t=="nanjing";
}
void misaka(){
    rep(i,1,n) pre[i]=suf[i]=0,s[i]=s[i+n]=0;
    scanf("%d%d%s",&n,&k,s+1);
    rep(i,1,n) s[i+n]=s[i];
    rep(i,7,n) pre[i]=max(pre[i-7]+ck(i-6),pre[i-1]);
    _rep(i,n-6,1) suf[i]=max(suf[i+7]+ck(i),suf[i+1]);
    int ans=pre[n];
    rep(i,1,min(k,n-1)){
        int cnt=0;
        rep(j,max(n-5,1),min(n+i-6,n)) cnt+=ck(j);
        ans=max(ans,suf[i+1]+pre[i]+cnt);
    }
    printf("%d\n",ans);
}
signed MISAKA(){
    int T=read();
    while(T--) misaka();
    return 0;
}