#include <bits/stdc++.h>
using namespace std;
string s;
string op = "nanjing";
void solve() {
    int n, k;
    cin >> n >> k;
    cin >> s;
    s = s + s;
    // cout << s << endl;
    int ans = 0;
    for (int i = 0; i <= min(7, k); ++i) {
        int cnt = 0;
        for (int j = i; j + 6 < n + i; ++j) {
            bool flag = 1;
            for (int kk = 0; kk < 7; ++kk) {
                if (op[kk] != s[j + kk]) {
                    flag = 0;
                    break;
                }
            }
            cnt += flag;
        }
        ans = max(ans, cnt);
    }
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}