#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (ll i = (l); i < (r); ++i)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using pl = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

int main(){
    ll nf;
    cin>>nf;
    rep(ia,0,nf){
        ll n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        string a="nanjing";
        ll f=min(k+1,(ll)10);
        ll ans=0;
        rep(j,0,f){
            ll zans=0;
            rep(i,0,n-6){
            ll b=0;
            rep(k,0,7){
                if(a[k]!=s[(i+k+j)%n])b=1;
            }
            if(b==0)zans++;
            }
            ans=max(ans,zans);
        }
        cout<<ans<<endl;
    }
}