#include<bits/stdc++.h>

#define endl "\n"
// #define int long long

using namespace std;

using i64 = long long;
using u64 = unsigned long long;

constexpr int N = 500, M = 2e6 + 10;
constexpr int P = 998244353;
constexpr int INF = 1e9;

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int ans = 0;
    for (int i = 0; i <= min(7, k); i++) {
        int res = 0;
        for (int j = 0; j < s.size(); j++) {
            if (s.substr(j, 7) == "nanjing") {
                res++;
            }
        }
        s += s.front();
        s.erase(s.begin());
        ans = max(ans, res);
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}