#include <bits/stdc++.h>
using namespace std;
int n, k;
string str;
int main(void) {
  cin.tie(nullptr)->sync_with_stdio(false);
  int tests; cin >> tests;
  while (tests--) {
    cin >> n >> k >> str;
    k = min(k, 7); int ans = 0;
    auto count = [&](string t)->int {
      int c = 0;
      for (int i = 0; i <= (int)t.size() - 7; ++i)
        c += (t.substr(i, 7) == "nanjing");
      return c;
    };
    for (int i = 0; i <= k; ++i) {
      ans = max(ans, count(str));
      str = str.substr(1) + str[0];
    } cout << ans << endl;
  }
  return 0;
} // main