#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

int work() {
    int n, k;
    std::cin >> n >> k;
    k = std::min(n, k);
    std::string S; std::cin >> S;
    S += S.substr(0, k);
    int l = S.size();
    std::vector<int> s(l, 0);
    for(int i = 0; i <= l - 7; ++i) s[i] = (S.substr(i, 7) == "nanjing");
    for(int i = 1; i < l; ++i) s[i] += s[i - 1];
    int ans = s[n - 7];
    for(int i = 0, j = n - 6; j < l; ++i, ++j) ans = std::max(ans, s[j] - s[i]);
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    int T; std::cin >> T; while(T--) std::cout << work() << char(10);
    return 0;
}