#include <iostream>
#include <vector>
using namespace std;

void slove() {
    int n, k;
    cin >> n >> k;
    k = min(n, k);

    string str;
    cin >> str;

    if (str.size() >= 7) {
        for (int i = 0; i < 6; i++) {
            str.push_back(str[i]);
        }
    }

    vector<int> in(str.size(), 0);

    int cnt = 0;
    for (int i = 0; i + 6 < str.size(); i++) {
        if (str.substr(i, 7) == "nanjing") {
            cnt++;
            for (int j = 1; j < 6; j++) in[i + j] = 1;
        }
    }

    if (str.size() >= 7) {
        for (int i = 0; i < 6; i++) {
            in[i] = in[str.size() - 6 + i];
        }
    }

    for (int i = 0; i <= k; i++) {
        if (!in[i]) {
            cout << cnt << "\n";
            return;
        }
    }
    cout << (cnt - 1) << "\n";
    return;
}

int main() {
    // freopen("in.txt" , "r" , stdin);
    int cnt = 1;
    cin >> cnt;

    while (cnt--) {
        slove();
    }
}