#include <bits/stdc++.h>

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

    int ans = 0;
    auto work = [&]() {
        int tmp = 0;
        for (int i = 0; i < n;) {
            if (i + 6 < n) {
                if (a.substr(i, 7) == "nanjing") {
                    i = i + 7;
                    tmp++;
                    continue;
                }
            } 
            i++;
        }
        ans = std::max(ans, tmp);
    };
    work();
    for (int i = 0; i < std::min(8, k); i++) {
        std::rotate(a.begin(), a.begin() + 1, a.end());        
        work();
        // std::cout << a << "\n";
    }
    std::cout << ans << "\n";

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

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
}