#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define rep2(i, l, r) for(ll i = l; i < r; i++)

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;

/* ---- */
#define all(A) A.begin(), A.end()
#define elif else if
using pii = pair<ll, ll>;

// bool chmin(auto &a, const auto &b) {return a > b ? a = b, 1 : 0;}
// bool chmax(auto &a, const auto &b) {return a < b ? a = b, 1 : 0;}

struct IOSetup {
  IOSetup() {
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
} iosetup;

template<class T>
void print(vector<T> a) {
  for (auto x : a) cerr << x << ' ';
  cerr << endl;
}



template<class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  cerr << head << ' ';
  print(forward<Tail>(tail)...);
}

void solve(){
  int n,k;
  cin>>n>>k;
  string s;
  cin>>s;
  vi a(n);
  rep(i,n)a[i]=s[i]-'a';
  string t="nanjing";
  vi b(7);
  rep(i,7)b[i]=t[i]-'a';


  int ans=0;
  rep(i,min(10,k+1)){
    // print(a);
    int cnt=0;
    rep(l,n-6){
      bool flag=true;
      rep(j,7){
        if(a[l+j]!=b[j])flag=false;
      }
      if(flag)cnt++;
    }
    ans=max(ans,cnt);
    vi c(n);
    rep(j,n){
      c[j]=a[(j+1)%n];
    }
    a=c;
  }
  cout<<ans<<'\n';
}

int main(){
  int T;
  cin>>T;
  rep(i,T)solve();
}