#include <bits/stdc++.h>

void solve() {
    int n, k;
    std::cin >> n >> k;
    std::string s;
    std::cin >> s;

    k = std::min(k, n - 1);
    s.resize(n + k);
    for (int i = n; i < n + k; ++i) s[i] = s[i - n];

    std::vector<int> ok(s.size());
    for (int i = 0; i + 6 < s.size(); ++i) {
        if (s.substr(i, 7) == "nanjing") {
            ok[i] = 1;
        }
    }

    int sum = 0;
    int L = n - 6;
    if (L <= 0) {
        std::cout << "0\n";
        return;
    }
    for (int i = 0; i < L; ++i) sum += ok[i];
    
    int ans = sum;
    for (int i = L; i < s.size(); ++i) {
        sum += ok[i];
        sum -= ok[i - L];
        ans = std::max(ans, sum);
    }

    std::cout << ans << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }
}