#include "bits/stdc++.h"
using namespace std;

#define ll long long 
#define INF 0x3f3f3f3f
#define LNF 0x3f3f3f3f3f3f3f3fll
#define MOD 998244353
#define pii pair<int, int>

#define N 100010
#define K 20

int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t; cin >> t;
    while (t --) {
        int n, k; cin >> n >> k;
        k = min(n, k);

        string s; cin >> s;
        s += s;

        vector<int> pos;

        for (int i = 0; i <= (2 * n) - 5; ++ i) {
            if (s.substr(i, 7) == "nanjing") {
                pos.emplace_back(i);
            }
        }

        int mx = 0, res = 0;

        for (int d = 0, l = 0, r = 0; d <= k; ++ d) {
            while (l < pos.size() && pos[l] < d) ++ l;
            while (r < pos.size() && pos[r] <= n + d - 5) ++ r;
            
            if (r - l > mx) {
                mx = r - l;
                res = d;
            }
        }

        cout << mx << '\n';
    }
}