#include <bits/stdc++.h>

using i64 = long long;

void sol() {
    int n, k;
    std::cin >> n >> k;

    std::string s;
    std::cin >> s;

    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'n' && s.substr(i, 7) == "nanjing") {
            cnt++;
        }
    }
    if  (n < 7) {
        std::cout << cnt << "\n";
        return;
    }
    for (int p = 1; p <= 6; p ++) {
        if (s.substr(n - (7 - p), 7 - p) + s.substr(0, p) == "nanjing" && p <= k) {cnt++;};
    }

    std::cout << cnt << "\n";
}

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

    int _ = 1;
    std::cin >> _;

    while (_--) {
        sol();
    }

    return 0;
}