#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl '\n'
#define log(...) (void(0))
#endif
using namespace std;
using ll = long long;
using lf = long double;
using ull = unsigned long long;

const int N = 500011;
string s, t = "nanjing";
int f[N];
int main() {
#ifdef memset0
  freopen("E.in", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);
  int task;
  cin >> task;
  while (task--) {
    int n, k;
    cin >> n >> k >> s;
    s = s + s;
    s.insert(s.begin(), '#');
    for (int i = 0; i < s.size(); ++i) f[i] = 0;
    for (int i = 1; i + t.size() - 1 < s.size(); ++i) {
      bool eq = 1;
      for (int k = 0; k < t.size(); ++k)
        if (s[i + k] != t[k]) {
          eq = 0;
          break;
        }
      if (eq) f[i] = f[i - 1] + 1;
      else
        f[i] = f[i - 1];
    }
    int ans = 0;
    for (int i = max(sz(t), n); i <= n + k && i < sz(s); ++i) ans = max(ans, f[i - t.size() + 1] - f[i - n]);
    cout << ans << '\n';
  }
  return 0;
}