#include<bits/stdc++.h>

#define int long long
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

void solve();

signed main() {
    fast
    int t = 1;
    cin >> t;
    while (t--) solve();
}

const int N = 1e2 + 10, M = 3e2 + 10, mod = 998244353;

int n, k;
string s;

int calc(const string &s){
    int cnt = 0;
    for(int j = 0; j < (int)s.size() - 6; j++){
        if(s.substr(j, 7) == "nanjing") cnt++;
    }
    return cnt;
}

void solve() {
    cin >> n >> k;
    cin >> s;
    int res = calc(s);
    for(int i = 0; i < min(k, 7ll); i++){
        auto c = s.front();
        s.erase(s.begin());
        s += c;
        res = max(res, calc(s));
    }
    cout << res << '\n';
}