#include <bits/stdc++.h>

using namespace std;


int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (int tc = (cin >> tc, tc); tc--; ) {
    int n, k; cin >> n >> k; k = min(k, n);
    string s; cin >> s;
    if (n < 7) { cout << "0\n"; continue; }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      bool nanjing = 1;
      for (int j = 0; j < 7 && nanjing; ++j) nanjing &= s[(i + j) % n] == "nanjing"[j];
      ans += nanjing;
    }
    int nans = 1;
    for (int i = 0; i < k; ++i) {
      bool bad = 0;
      for (int di = -6; di < 0; ++di) {
        bool nanjing = 1;
        for (int j = 0; j < 7 && nanjing; ++j) nanjing &= s[(i + n + di + j) % n] == "nanjing"[j];
        bad |= nanjing;
      }
      nans &= bad;
    }
    cout << ans - nans << '\n';
  }
}