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

void solve() {
   int n, k;
   cin >> n >> k;
   string s;
   cin >> s;
   k = min(n, k);
   k = min(7, k);
   int ans = 0;
   if (n < 7) {
      cout << 0 << endl;
      return;
   }
   if (k != 0)
   s += s.substr(0, k);
   int mx = 0;
   // cerr << k << endl;
   for (int i = 0; i <= k; i++) {
      ans = 0;
      for (int j = i; j < n + i; j++) {
         if (s.substr(j, 7) == "nanjing") ans++;
      }
      // cerr << ans << endl;
      mx = max(mx, ans);
   }
   cout << mx << endl;
   
}
signed main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   int t;
   cin >> t;
   while (t--) {
      solve();
   }
}